Linear vs. semidefinite extended formulations
From MaRDI portal
Publication:5415468
DOI10.1145/2213977.2213988zbMath1286.90125WikidataQ56815274 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 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
Statistical Query Algorithms for Mean Vector Estimation and Stochastic Convex Optimization, Matrices of Bounded Psd Rank are Easy to Detect, The Nonnegative Rank of a Matrix: Hard Problems, Easy Solutions, A separation between tropical matrix ranks, Regular Matroids Have Polynomial Extension Complexity, Approximate tensor decompositions: Disappearance of many separations, The Slack Realization Space of a Polytope, Size-degree trade-offs for sums-of-squares and positivstellensatz proofs, Forbidden Vertices, The Complexity of Positive Semidefinite Matrix Factorization, Positive semidefinite rank and nested spectrahedra, Deriving compact extended formulations via LP-based separation techniques, 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, Extended formulations from communication protocols in output-efficient time, Clique-stable set separation in perfect graphs with no balanced skew-partitions, Rank functions of tropical matrices, Heuristics for exact nonnegative matrix factorization, 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, Polytopes of minimum positive semidefinite rank, Clique versus independent set, On the nonnegative rank of distance matrices, 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, 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, The matching problem has no small symmetric SDP, The parity Hamiltonian cycle problem, Maximum semidefinite and linear extension complexity of families of polytopes, Decomposition techniques applied to the clique-stable set separation problem, Affine reductions for LPs and SDPs, Rational and real positive semidefinite rank can be different, Algorithms for positive semidefinite factorization, Strong reductions for extended formulations, Factoring a band matrix over a semiring, New limits of treewidth-based tractability in optimization, A variational principle for ground spaces, On \(\epsilon\)-sensitive monotone computations, Lifts of non-compact convex sets and cone factorizations, Nonnegative rank depends on the field, \(k\)-neighborly faces of the Boolean quadric polytopes, The common face of some 0/1-polytopes with NP-complete nonadjacency relation, Extended formulations for radial cones, 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, The rectangle covering number of random Boolean matrices, Some \(0/1\) polytopes need exponential size extended formulations, A note on the extension complexity of the knapsack polytope, Polynomial size IP formulations of knapsack may require exponentially large coefficients, 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, The Parity Hamiltonian Cycle Problem in Directed Graphs, Deciding Polyhedrality of Spectrahedra, Nondeterministic Communication Complexity of Random Boolean Functions (Extended Abstract), Tropical lower bound for extended formulations. II. Deficiency graphs of matrices, Mixed states in one spatial dimension: Decompositions and correspondence with nonnegative matrices, 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
