Linear vs. semidefinite extended formulations
From MaRDI portal
Publication:5415468
DOI10.1145/2213977.2213988zbMath1286.90125OpenAlexW2119368733WikidataQ56815274 ScholiaQ56815274MaRDI QIDQ5415468
Samuel Fiorini, Sebastian Pokutta, Hans Raj Tiwary, Serge Massar, Ronald de Wolf
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 programmingsemidefinite programmingcombinatorial optimizationcommunication complexityquantum communication complexity
Linear programming (90C05) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
Clique-stable set separation in perfect graphs with no balanced skew-partitions ⋮ Rank functions of tropical matrices ⋮ The rectangle covering number of random Boolean matrices ⋮ Heuristics for exact nonnegative matrix factorization ⋮ Query Complexity in Expectation ⋮ Approximation Limits of Linear Programs (Beyond Hierarchies) ⋮ A separation between tropical matrix ranks ⋮ Conic Approach to Quantum Graph Parameters Using Linear Optimization Over the Completely Positive Semidefinite Cone ⋮ Global completability with applications to self-consistent quantum tomography ⋮ Extended formulations for independence polytopes of regular matroids ⋮ Common information and unique disjointness ⋮ Average case polyhedral complexity of the maximum stable set problem ⋮ Regular Matroids Have Polynomial Extension Complexity ⋮ Polynomial size IP formulations of knapsack may require exponentially large coefficients ⋮ Statistical Query Algorithms for Mean Vector Estimation and Stochastic Convex Optimization ⋮ Polytopes of minimum positive semidefinite rank ⋮ Matrices of Bounded Psd Rank are Easy to Detect ⋮ The matching problem has no small symmetric SDP ⋮ Deciding Polyhedrality of Spectrahedra ⋮ Lifts for Voronoi cells of lattices ⋮ Clique versus independent set ⋮ The Nonnegative Rank of a Matrix: Hard Problems, Easy Solutions ⋮ Shadows of Newton polytopes ⋮ The parity Hamiltonian cycle problem ⋮ Lower bounds on the sizes of integer programs without additional variables ⋮ Simple extensions of polytopes ⋮ The Complexity of Positive Semidefinite Matrix Factorization ⋮ Self-Dual Polyhedral Cones and Their Slack Matrices ⋮ A variational principle for ground spaces ⋮ On \(\epsilon\)-sensitive monotone computations ⋮ Maximum semidefinite and linear extension complexity of families of polytopes ⋮ Some \(0/1\) polytopes need exponential size extended formulations ⋮ On the nonnegative rank of distance matrices ⋮ Decomposition techniques applied to the clique-stable set separation problem ⋮ Positive semidefinite rank and nested spectrahedra ⋮ Affine reductions for LPs and SDPs ⋮ Deriving compact extended formulations via LP-based separation techniques ⋮ Lifts of non-compact convex sets and cone factorizations ⋮ Nondeterministic Communication Complexity of Random Boolean Functions (Extended Abstract) ⋮ A note on the extension complexity of the knapsack polytope ⋮ Nonnegative rank depends on the field ⋮ Mixed states in one spatial dimension: Decompositions and correspondence with nonnegative matrices ⋮ Approximate tensor decompositions: Disappearance of many separations ⋮ Cutting planes from extended LP formulations ⋮ On the linear extension complexity of regular \(n\)-gons ⋮ On the \({\mathcal {H}}\)-free extension complexity of the TSP ⋮ Deriving compact extended formulations via LP-based separation techniques ⋮ \(k\)-neighborly faces of the Boolean quadric polytopes ⋮ The common face of some 0/1-polytopes with NP-complete nonadjacency relation ⋮ An Almost Optimal Algorithm for Computing Nonnegative Rank ⋮ Extended formulations in combinatorial optimization ⋮ A Polyhedral Characterization of Border Bases ⋮ Quantum learning of classical stochastic processes: The completely positive realization problem ⋮ The Slack Realization Space of a Polytope ⋮ A Comprehensive Analysis of Polyhedral Lift-and-Project Methods ⋮ Rational and real positive semidefinite rank can be different ⋮ Algorithms for positive semidefinite factorization ⋮ Factoring a band matrix over a semiring ⋮ Strong reductions for extended formulations ⋮ Extended formulations for radial cones ⋮ Mixed Integer Linear Programming Formulation Techniques ⋮ Extended formulations from communication protocols in output-efficient time ⋮ 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 ⋮ Size-degree trade-offs for sums-of-squares and positivstellensatz proofs ⋮ The Parity Hamiltonian Cycle Problem in Directed Graphs ⋮ Tropical lower bound for extended formulations. II. Deficiency graphs of matrices ⋮ Forbidden Vertices ⋮ 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 ⋮ New limits of treewidth-based tractability in optimization
