The Matching Polytope has Exponential Extension Complexity
From MaRDI portal
Publication:4640350
DOI10.1145/3127497zbMath1426.90255arXiv1311.2369OpenAlexW2759253428WikidataQ115522540 ScholiaQ115522540MaRDI QIDQ4640350
Publication date: 17 May 2018
Published in: Journal of the ACM, Proceedings of the forty-sixth annual ACM symposium on Theory of computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1311.2369
linear programmingpolytopescombinatorial optimizationmatchinglinear programming relaxationsextension complexity
Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Linear programming (90C05) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)
Related Items (94)
Sparktope: linear programs from algorithms ⋮ Heuristics for exact nonnegative matrix factorization ⋮ Lifting for Simplicity: Concise Descriptions of Convex Sets ⋮ Query Complexity in Expectation ⋮ Sum-of-squares rank upper bounds for matching problems ⋮ Approximation Limits of Linear Programs (Beyond Hierarchies) ⋮ Integrality gaps for strengthened linear relaxations of capacitated facility location ⋮ Self-scaled bounds for atomic cone ranks: applications to nonnegative rank and cp-rank ⋮ Some complete and intermediate polynomials in algebraic complexity theory ⋮ Extended formulations for independence polytopes of regular matroids ⋮ Common information and unique disjointness ⋮ Average case polyhedral complexity of the maximum stable set problem ⋮ Quasi-Popular Matchings, Optimality, and Extended Formulations ⋮ Regular Matroids Have Polynomial Extension Complexity ⋮ Theoretical insights and algorithmic tools for decision diagram-based optimization ⋮ Erdős-Ko-Rado for perfect matchings ⋮ Extension complexity of low-dimensional polytopes ⋮ On the extension complexity of scheduling polytopes ⋮ Statistical Query Algorithms for Mean Vector Estimation and Stochastic Convex Optimization ⋮ The matching problem has no small symmetric SDP ⋮ Limitations of the hyperplane separation technique for bounding the extension complexity of polytopes ⋮ Extended formulations for matroid polytopes through randomized protocols ⋮ Parameterized extension complexity of independent set and related problems ⋮ On the combinatorial lower bound for the extension complexity of the spanning tree polytope ⋮ Lifts for Voronoi cells of lattices ⋮ Shadows of Newton polytopes ⋮ ReLU neural networks of polynomial size for exact maximum flow computation ⋮ Complex psd-minimal polytopes in dimensions two and three ⋮ On Ranks of Regular Polygons ⋮ Approximate nonnegative rank is equivalent to the smooth rectangle bound ⋮ Lower bounds on the sizes of integer programs without additional variables ⋮ Simple extensions of polytopes ⋮ From Duels to Battlefields: Computing Equilibria of Blotto and Other Games ⋮ The Frank-Wolfe algorithm: a short introduction ⋮ Polyhedral techniques in combinatorial optimization: matchings and tours ⋮ The role of rationality in integer-programming relaxations ⋮ Complexity of combinatorial optimization problems in terms of face lattices of associated polytopes ⋮ On permuting some coordinates of polytopes ⋮ On \(\epsilon\)-sensitive monotone computations ⋮ Approximate Douglas-Rachford algorithm for two-sets convex feasibility problems ⋮ A polyhedral perspective on tropical convolutions ⋮ Extended formulation for CSP that is compact for instances of bounded treewidth ⋮ Maximum semidefinite and linear extension complexity of families of polytopes ⋮ Extension Complexity of Independent Set Polytopes ⋮ Decomposition techniques applied to the clique-stable set separation problem ⋮ Positive semidefinite rank and nested spectrahedra ⋮ Cuts in undirected graphs. II ⋮ Affine reductions for LPs and SDPs ⋮ The Ramping Polytope and Cut Generation for the Unit Commitment Problem ⋮ Learning in Combinatorial Optimization: What and How to Explore ⋮ Strengthening convex relaxations of 0/1-sets using Boolean formulas ⋮ A geometric lower bound on the extension complexity of polytopes based on the \(f\)-vector ⋮ Extension complexity and realization spaces of hypersimplices ⋮ Cutting planes from extended LP formulations ⋮ On the linear extension complexity of regular \(n\)-gons ⋮ Some upper and lower bounds on PSD-rank ⋮ Circuit and bond polytopes on series-parallel graphs ⋮ On the \({\mathcal {H}}\)-free extension complexity of the TSP ⋮ Smaller extended formulations for the spanning tree polytope of bounded-genus graphs ⋮ An Almost Optimal Algorithm for Computing Nonnegative Rank ⋮ Information-theoretic approximations of the nonnegative rank ⋮ Parameterized shifted combinatorial optimization ⋮ The Slack Realization Space of a Polytope ⋮ A Comprehensive Analysis of Polyhedral Lift-and-Project Methods ⋮ Extended formulations for vertex cover ⋮ Exponential Lower Bounds for Polytopes in Combinatorial Optimization ⋮ A Parametrized Analysis of Algorithms on Hierarchical Graphs ⋮ Separation routine and extended formulations for the stable set problem in claw-free graphs ⋮ Strong reductions for extended formulations ⋮ Extended formulations for radial cones ⋮ Mixed Integer Linear Programming Formulation Techniques ⋮ Alternating conditional gradient method for convex feasibility problems ⋮ Extended formulations from communication protocols in output-efficient time ⋮ Computing the nucleolus of weighted cooperative matching games in polynomial time ⋮ Balas formulation for the union of polytopes is optimal ⋮ Lower bounds on nonnegative rank via nonnegative nuclear norms ⋮ On the existence of 0/1 polytopes with high semidefinite extension complexity ⋮ The Minimum Euclidean-Norm Point in a Convex Polytope: Wolfe's Combinatorial Algorithm is Exponential ⋮ No Small Linear Program Approximates Vertex Cover Within a Factor 2 − ɛ ⋮ Compact linear programs for 2SAT ⋮ On the linear extension complexity of stable set polytopes for perfect graphs ⋮ Polynomial size linear programs for problems in \textsc{P} ⋮ The slack realization space of a matroid ⋮ Sum-of-Squares Rank Upper Bounds for Matching Problems ⋮ Unnamed Item ⋮ Extension complexity of formal languages ⋮ Lower bounds on matrix factorization ranks via noncommutative polynomial optimization ⋮ Extended formulations of lower-truncated transversal polymatroids ⋮ Tropical lower bound for extended formulations. II. Deficiency graphs of matrices ⋮ Individual and cooperative portfolio optimization as linear program ⋮ A short proof that the extension complexity of the correlation polytope grows exponentially ⋮ A generalization of extension complexity that captures P ⋮ On Polyhedral Approximations of the Positive Semidefinite Cone ⋮ New limits of treewidth-based tractability in optimization
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Efficient algorithms for privately releasing marginals via convex relaxations
- The Geometry of Differential Privacy: The Small Database and Approximate Cases
- Faster Algorithms for Privately Releasing Marginals
- Private Learning and Sanitization: Pure vs. Approximate Differential Privacy
- Privately Releasing Conjunctions and the Statistical Query Barrier
- On the geometry of differential privacy
- Interactive privacy via the median mechanism
- The price of privately releasing contingency tables and the spectra of random matrices with correlated rows
- Lower Bounds in Differential Privacy
- Iterative Constructions and Private Data Release
- Characterizing the sample complexity of private learners
- Faster private release of marginals on small databases
- Bounds on the Sample Complexity for Private Learning and Private Data Release
- Differential Privacy and the Fat-Shattering Dimension of Linear Queries
- Our Data, Ourselves: Privacy Via Distributed Noise Generation
- New Efficient Attacks on Statistical Disclosure Control Mechanisms
- Collusion-secure fingerprinting for digital data
- On the complexity of differentially private data release
- Advances in Cryptology – CRYPTO 2004
- Answering n {2+o(1)} counting queries with differential privacy is hard
- Theory of Cryptography
This page was built for publication: The Matching Polytope has Exponential Extension Complexity
