-
作者：Briet, Jop; Dadush, Daniel; Pokutta, Sebastian
作者单位：New York University; University System of Georgia; Georgia Institute of Technology
摘要：In Rothvo (Math Program 142(1-2):255-268, 2013) it was shown that there exists a 0/1 polytope (a polytope whose vertices are in ) such that any higher-dimensional polytope projecting to it must have facets, i.e., its linear extension complexity is exponential. The question whether there exists a 0/1 polytope with high positive semidefinite extension complexity was left open. We answer this question in the affirmative by showing that there is a 0/1 polytope such that any spectrahedron projectin...
-
作者：Shitov, Yaroslav
作者单位：HSE University (National Research University Higher School of Economics)
摘要：The tropical arithmetic operations on , defined as and , arise from studying the geometry over non-Archimedean fields. We present an application of tropical methods to the study of extended formulations for convex polytopes. We propose a non-Archimedean generalization of the well known Boolean rank bound for the extension complexity. We show how to construct a real polytope with the same extension complexity and combinatorial type as a given non-Archimedean polytope. Our results allow us to de...
-
作者：Pilanci, Mert; Wainwright, Martin J.; El Ghaoui, Laurent
作者单位：University of California System; University of California Berkeley; University of California System; University of California Berkeley
摘要：We introduce novel relaxations for cardinality-constrained learning problems, including least-squares regression as a special but important case. Our approach is based on reformulating a cardinality-constrained problem exactly as a Boolean program, to which standard convex relaxations such as the Lasserre and Sherali-Adams hierarchies can be applied. We analyze the first-order relaxation in detail, deriving necessary and sufficient conditions for exactness in a unified manner. In the special c...
-
作者：Mahjoub, A. Ridha; Rinaldi, Giovanni; Woeginger, Gerhard
作者单位：Universite PSL; Universite Paris-Dauphine; Consiglio Nazionale delle Ricerche (CNR); Istituto di Analisi dei Sistemi ed Informatica Antonio Ruberti (IASI-CNR); Eindhoven University of Technology
-
作者：Fawzi, Hamza; Parrilo, Pablo A.
作者单位：Massachusetts Institute of Technology (MIT)
摘要：The nonnegative rank of an entrywise nonnegative matrix is the smallest integer such that can be written as where and are both nonnegative. The nonnegative rank arises in different areas such as combinatorial optimization and communication complexity. Computing this quantity is NP-hard in general and it is thus important to find efficient bounding techniques especially in the context of the aforementioned applications. In this paper we propose a new lower bound on the nonnegative rank which, u...
-
作者：Burer, Samuel; Yang, Boshi
作者单位：University of Iowa; University of Iowa
摘要：This paper studies an extended trust region subproblem (eTRS) in which the trust region intersects the unit ball with linear inequality constraints. When , or and the linear constraints are parallel, it is known that the eTRS optimal value equals the optimal value of a particular convex relaxation, which is solvable in polynomial time. However, it is also known that, when and at least two of the linear constraints intersect within the ball, i.e., some feasible point of the eTRS satisfies both ...
-
作者：Chakrabarti, Amit; Kale, Sagar
作者单位：Dartmouth College
摘要：We study the problem of finding a maximum matching in a graph given by an input stream listing its edges in some arbitrary order, where the quantity to be maximized is given by a monotone submodular function on subsets of edges. This problem, which we call maximum submodular-function matching (MSM), is a natural generalization of maximum weight matching (MWM), which is in turn a generalization of maximum cardinality matching. We give two incomparable algorithms for this problem with space usag...
-
作者：Kaibel, Volker; Weltge, Stefan
作者单位：Otto von Guericke University
摘要：Let be the set of integer points in some polyhedron. We investigate the smallest number of facets of any polyhedron whose set of integer points is . This quantity, which we call the relaxation complexity of , corresponds to the smallest number of linear inequalities of any integer program having as the set of feasible solutions that does not use auxiliary variables. We show that the use of auxiliary variables is essential for constructing polynomial size integer programming formulations in man...
-
作者：Mnich, Matthias; Wiese, Andreas
作者单位：Max Planck Society
摘要：Fixed-parameter tractability analysis and scheduling are two core domains of combinatorial optimization which led to deep understanding of many important algorithmic questions. However, even though fixed-parameter algorithms are appealing for many reasons, no such algorithms are known for many fundamental scheduling problems. In this paper we present the first fixed-parameter algorithms for classical scheduling problems such as makespan minimization, scheduling with job-dependent cost function...
-
作者：Carnes, Tim; Shmoys, David B.
作者单位：Cornell University; Cornell University
摘要：Primal-dual algorithms have played an integral role in recent developments in approximation algorithms, and yet there has been little work on these algorithms in the context of LP relaxations that have been strengthened by the addition of more sophisticated valid inequalities. We introduce primal-dual schema based on the LP relaxations devised by Carr et al. for the minimum knapsack problem as well as for the single-demand capacitated facility location problem. Our primal-dual algorithms achie...
