-
作者：Gaar, Elisabeth; Lee, Jon; Ljubic, Ivana; Sinnl, Markus; Taninmis, Kuebra
作者单位：Johannes Kepler University Linz; Johannes Kepler University Linz; University of Michigan System; University of Michigan; ESSEC Business School
摘要：We study a class of integer bilevel programs with second-order cone constraints at the upper-level and a convex-quadratic objective function and linear constraints at the lower-level. We develop disjunctive cuts (DCs) to separate bilevel-infeasible solutions using a second-order-cone-based cut-generating procedure. We propose DC separation strategies and consider several approaches for removing redundant disjunctions and normalization. Using these DCs, we propose a branch-and-cut algorithm for...
-
作者：Aziz, Haris; Li, Bo; Wu, Xiaowei
作者单位：University of New South Wales Sydney; Hong Kong Polytechnic University; University of Macau
摘要：We initiate the work on maximin share (MMS) fair allocation of m indivisible chores to n agents using only their ordinal preferences, from both algorithmic and mechanism design perspectives. The previous best-known approximation ratio using ordinal preferences is 2 - 1/n by Aziz et al. [AAAI 2017]. We improve this result by giving a deterministic 5/3-approximation algorithm that determines an allocation sequence of agents, according to which items are allocated one by one. By a tighter analysi...
-
作者：Das Gupta, Shuvomoy; Van Parys, Bart P. G.; Ryu, Ernest K.
作者单位：Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT); Seoul National University (SNU)
摘要：We present the Branch-and-Bound Performance Estimation Programming (BnB-PEP), a unified methodology for constructing optimal first-order methods for convex and nonconvex optimization. BnB-PEP poses the problem of finding the optimal optimization method as a nonconvex but practically tractable quadratically constrained quadratic optimization problem and solves it to certifiable global optimality using a customized branch-and-bound algorithm. By directly confronting the nonconvexity, BnB-PEP off...
-
作者：di Serafino, Daniela; Hager, William W. W.; Toraldo, Gerardo; Viola, Marco
作者单位：University of Naples Federico II; State University System of Florida; University of Florida; Universita della Campania Vanvitelli; University College Dublin
摘要：For polyhedral constrained optimization problems and a feasible point x, it is shown that the projection of the negative gradient on the tangent cone, denoted del(Omega) f(x), has an orthogonal decomposition of the form beta(x) + phi(x). At a stationary point, del(Omega) f(x) = 0 so parallel to del(Omega) f(x)parallel to reflects the distance to a stationary point. Away from a stationary point, parallel to beta(x)parallel to and parallel to phi(x)parallel to measure different aspects of optima...
-
作者：Sorin, Sylvain
作者单位：Sorbonne Universite; Centre National de la Recherche Scientifique (CNRS); CNRS - National Institute for Mathematical Sciences (INSMI); Universite Paris Cite
摘要：The purpose of this article is to underline the links between some no-regret algorithms used in on-line learning, games and convex optimization and to compare the continuous and discrete time versions.
-
作者：Ashkenazi-Golan, Galit; Krasikov, Ilia; Rainer, Catherine; Solan, Eilon
作者单位：University of London; London School Economics & Political Science; HSE University (National Research University Higher School of Economics); Centre National de la Recherche Scientifique (CNRS); Universite de Bretagne Occidentale
摘要：We study quitting games and introduce an alternative notion of strategy profiles- absorption paths. An absorption path is parametrized by the total probability of absorption in past play rather than by time, and it accommodates both discrete-time aspects and continuous-time aspects. We then define the concept of sequentially 0-pelfect absorption paths, which are shown to be limits of epsilon-equilibrium strategy profiles as epsilon goes to 0. We establish that all quitting games that do not ha...
-
作者：Wei, Ningji; Zhang, Peter
作者单位：Texas Tech University System; Texas Tech University; Carnegie Mellon University
摘要：We investigate the concept of adjustability-the difference in objective values between two types of dynamic robust optimization formulations: one where (static) decisions are made before uncertainty realization, and one where uncertainty is resolved before (adjustable) decisions. This difference reflects the value of information and decision timing in optimization under uncertainty, and is related to several other concepts such as the optimality of decision rules in robust optimization. We dev...
-
作者：Farhadi, Majid; Gupta, Swati; Sun, Shengding; Tetali, Prasad; Wigal, Michael C.
作者单位：University System of Georgia; Georgia Institute of Technology; Massachusetts Institute of Technology (MIT); Carnegie Mellon University
摘要：The minimum linear ordering problem (MLOP) generalizes well-known combinatorial optimization problems such as minimum linear arrangement and minimum sum set cover. MLOP seeks to minimize an aggregated cost f (center dot) due to an ordering sigma of the items (say [n]), i.e., min(sigma) Sigma(i is an element of n]) f (E-i,E- sigma), where E-i,E- sigma is the set of items mapped by s to indices [i]. Despite an extensive literature on MLOP variants and approximations for these, it was unclear whe...
-
作者：Aziz, Haris; Baychkov, Anton; Biro, Peter
作者单位：University of New South Wales Sydney; University of Sydney; HUN-REN; HUN-REN Centre for Economic & Regional Studies; Corvinus University Budapest
摘要：We introduce a new two-sided stable matching problem that describes the summer internship matching practice of an Australian university. The model is a case between two models of Kamada and Kojima on matchings with distributional constraints. We study three solution concepts, the strong and weak stability concepts proposed by Kamada and Kojima, and a new one in between the two, called cutoff stability. Kamada and Kojima showed that a strongly stable matching may not exist in their most restric...
-
作者：Thomson, William; Velez, Rodrigo A.
作者单位：University of Rochester
摘要：In a queueing problem , a group of agents are waiting for a service. Each agent incurs a cost of waiting that is proportional to the time they wait. Monetary transfers can take place. We study the subsolutions of the no-envy solution that are anonymous, consistent, conversely consistent, and continuous. We show that there are infinitely many proper consistent subsolutions from the no-envy solution and characterize a class of these solutions on the basis of basic requirements of continuity, ano...
