-
作者：Lyu, Bochuan; Hicks, Illya V.; Huchette, Joey
作者单位：Rice University; Alphabet Inc.; Google Incorporated
摘要：We introduce techniques to build small ideal mixed-integer programming (MIP) formulations of combinatorial disjunctive constraints (CDCs) via the independent branching scheme. We present a novel pairwise IB-representable class of CDCs, CDCs admitting junction trees, and provide a combinatorial procedure to build MIP formu-lations for those constraints. Generalized special ordered sets (SOS k) can be modeled by CDCs admitting junction trees and we also obtain MIP formulations of SOS k. Furtherm...
-
作者：Caragiannis, Ioannis; Filos-Ratsikas, Aris; Frederiksen, Soren Kristoffer Stiil; Hansen, Kristoffer Arnsfelt; Tan, Zihan
作者单位：Aarhus University; University of Edinburgh; Rutgers University System; Rutgers University Newark; Rutgers University New Brunswick
摘要：We study the truthful facility assignment problem, where a set of agents with private most-preferred points on a metric space have to be assigned to facilities that lie on the metric space, under capacity constraints on the facilities. The goal is to produce such an assignment that minimizes the social cost, i.e., the total distance between the most-preferred points of the agents and their corresponding facilities in the assignment, under the constraint of truthfulness, which ensures that agen...
-
作者：Grabisch, Michel; Sudholter, Peter
作者单位：heSam Universite; Universite Pantheon-Sorbonne; Paris School of Economics; University of Southern Denmark
摘要：A balanced transferable utility game (N, v) has a stable core if its core is externally stable, that is, if each imputation that is not in the core is dominated by some core element. Given two payoff allocations x and y, we say that xoutvotesy via some coalition S of a feasible set if x dominates y via S and x allocates at least v(T) to any feasible T that is not contained in S. It turns out that outvoting is transitive and the set M of maximal elements with respect to outvoting coincides with...
-
作者：Cominetti, Roberto; Dose, Valerio; Scarsini, Marco
作者单位：Universidad Adolfo Ibanez; Sapienza University Rome; Luiss Guido Carli University
摘要：The price of anarchy has become a standard measure of the efficiency of equilibria in games. Most of the literature in this area has focused on establishing worst-case bounds for specific classes of games, such as routing games or more general congestion games. Recently, the price of anarchy in routing games has been studied as a function of the traffic demand, providing asymptotic results in light and heavy traffic. The aim of this paper is to study the price of anarchy in nonatomic routing g...
-
作者：Baiou, Mourad; Correa, Jose; Laraki, Rida
作者单位：Universite Clermont Auvergne (UCA); Centre National de la Recherche Scientifique (CNRS); Polytechnic Institute of Clermont Auvergne; IMT - Institut Mines-Telecom; Mines Saint-Etienne; Universidad de Chile; Centre National de la Recherche Scientifique (CNRS); Universite PSL; Universite Paris-Dauphine
-
作者：Audet, Charles; Bouchet, Pierre-Yves; Bourdin, Loic
作者单位：Universite de Montreal
摘要：This note provides a counterexample to a theorem announced in the last part of the paper (Vicente and Custodio Math Program 133:299-325, 2012). The counterexample involves an objective function f : R -> R which satisfies all the assumptions required by the theorem but contradicts some of its conclusions. A corollary of this theorem is also affected by this counterexample. The main flaw revealed by the counterexample is the possibility that a directional direct search method (dDSM) generates a ...
-
作者：Bredies, Kristian; Carioni, Marcello; Fanzon, Silvio; Walter, Daniel
作者单位：University of Graz; University of Twente; University of Hull; Humboldt University of Berlin
摘要：We propose a fully-corrective generalized conditional gradient method (FC-GCG) for the minimization of the sum of a smooth, convex loss function and a convex one homogeneous regularizer over a Banach space. The algorithm relies on the mutual update of a finite set Ak of extremal points of the unit ball of the regularizer and of an iterate uk ? cone(Ak). Each iteration requires the solution of one linear problem to update Ak and of one finite dimensional convex minimization problem to update th...
-
作者：Das Gupta, Shuvomoy; Van Parys, Bart P. G.; Ryu, Ernest K.
作者单位：Massachusetts Institute of Technology (MIT); Seoul National University (SNU)
-
作者：Lourenco, Bruno F.; Roshchina, Vera; Saunderson, James
作者单位：Research Organization of Information & Systems (ROIS); Institute of Statistical Mathematics (ISM) - Japan; University of New South Wales Sydney; Monash University
摘要：Amenability is a notion of facial exposedness for convex cones that is stronger than being facially dual complete (or 'nice') which is, in turn, stronger than merely being facially exposed. Hyperbolicity cones are a family of algebraically structured closed convex cones that contain all spectrahedral cones (linear sections of positive semidefinite cones) as special cases. It is known that all spectrahedral cones are amenable. We establish that all hyperbolicity cones are amenable. As part of t...
-
作者：Ferhat, Dehia Ait; Kiraly, Zoltan; Sebo, Andras; Stauffer, Gautier
作者单位：Mentor Graphics Inc; Eotvos Lorand University; Communaute Universite Grenoble Alpes; Universite Grenoble Alpes (UGA); University of Lausanne
摘要：Given an undirected graph, are there k matchings whose union covers all of its nodes, that is, a matching-k-cover? When k = 1, the problem is equivalent to the existence of a perfect matching for which Tutte's celebrated matching theorem (J. Lon. Math. Soc., 1947) provides a `good' characterization. We prove here, when k is greater than one, a `good' characterization a la Konig: for k >= 2, there exist k matchings covering every node if and only if for every stable set S, we have vertical bar ...
