Linear vs. semidefinite extended formulations
From MaRDI portal
Publication:5415468
DOI10.1145/2213977.2213988zbMath1286.90125WikidataQ56815274 ScholiaQ56815274MaRDI QIDQ5415468
Samuel Fiorini, Sebastian Pokutta, Hans Raj Tiwary, Ronald de Wolf, Serge Massar
Publication date: 13 May 2014
Published in: Proceedings of the forty-fourth annual ACM symposium on Theory of computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/2213977.2213988
linear programming; semidefinite programming; combinatorial optimization; communication complexity; quantum communication complexity
90C05: Linear programming
90C27: Combinatorial optimization
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Related Items
Forbidden Vertices, Deriving compact extended formulations via LP-based separation techniques, An Almost Optimal Algorithm for Computing Nonnegative Rank, Extended formulations in combinatorial optimization, A Polyhedral Characterization of Border Bases, Clique-stable set separation in perfect graphs with no balanced skew-partitions, Rank functions of tropical matrices, Heuristics for exact nonnegative matrix factorization, Polytopes of minimum positive semidefinite rank, Clique versus independent set, On the nonnegative rank of distance matrices, Smallest compact formulation for the permutahedron, Extended formulations, nonnegative factorizations, and randomized communication protocols, On the extension complexity of combinatorial polytopes, On the existence of 0/1 polytopes with high semidefinite extension complexity, Uncapacitated flow-based extended formulations, Positive semidefinite rank, Worst-case results for positive semidefinite rank, Lower bounds on the sizes of integer programs without additional variables, Simple extensions of polytopes, \(k\)-neighborly faces of the Boolean quadric polytopes, The common face of some 0/1-polytopes with NP-complete nonadjacency relation, A short proof that the extension complexity of the correlation polytope grows exponentially, An upper bound for nonnegative rank, A generalization of extension complexity that captures P, The simplest families of polytopes associated with NP-hard problems, Some \(0/1\) polytopes need exponential size extended formulations, A note on the extension complexity of the knapsack polytope, Quantum learning of classical stochastic processes: The completely positive realization problem, A Comprehensive Analysis of Polyhedral Lift-and-Project Methods, Mixed Integer Linear Programming Formulation Techniques, Deciding Polyhedrality of Spectrahedra, Query Complexity in Expectation, Approximation Limits of Linear Programs (Beyond Hierarchies), Conic Approach to Quantum Graph Parameters Using Linear Optimization Over the Completely Positive Semidefinite Cone
