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
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
