On the extension complexity of combinatorial polytopes
From MaRDI portal
DOI10.1007/978-3-642-39206-1_6zbMath1336.90095arXiv1302.2340OpenAlexW1942134738MaRDI QIDQ745682
Publication date: 14 October 2015
Published in: Mathematical Programming. Series A. Series B, Automata, Languages, and Programming (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1302.2340
Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Abstract computational complexity for mathematical programming problems (90C60)
Related Items (23)
Some complete and intermediate polynomials in algebraic complexity theory ⋮ Common information and unique disjointness ⋮ Average case polyhedral complexity of the maximum stable set problem ⋮ On the extension complexity of scheduling polytopes ⋮ Parameterized extension complexity of independent set and related problems ⋮ The last dozen of years of or research in Czechia and Slovakia ⋮ Lower bounds on the sizes of integer programs without additional variables ⋮ Simple extensions of polytopes ⋮ On permuting some coordinates of polytopes ⋮ Maximum semidefinite and linear extension complexity of families of polytopes ⋮ Extension Complexity of Independent Set Polytopes ⋮ Unnamed Item ⋮ A note on the extension complexity of the knapsack polytope ⋮ On the \({\mathcal {H}}\)-free extension complexity of the TSP ⋮ Exponential Lower Bounds for Polytopes in Combinatorial Optimization ⋮ Extended formulations for radial cones ⋮ Pitch, extension complexity, and covering problems ⋮ Polynomial size linear programs for problems in \textsc{P} ⋮ Extension complexity of formal languages ⋮ Extended formulations for convex hulls of some bilinear functions ⋮ A short proof that the extension complexity of the correlation polytope grows exponentially ⋮ A generalization of extension complexity that captures P ⋮ New limits of treewidth-based tractability in optimization
Cites Work
- Unnamed Item
- Unnamed Item
- The max-cut problem on graphs not contractible to \(K_ 5\)
- Expressing combinatorial optimization problems by linear programs
- On the distributional complexity of disjointness
- Some simplified NP-complete graph problems
- A note on the extension complexity of the knapsack polytope
- Generating facets for the cut polytope of a graph by triangular elimination
- Lectures on Polytopes
- Nondeterministic Quantum Query and Communication Complexities
- Reducibility among Combinatorial Problems
- Linear vs. semidefinite extended formulations
- Two-party Bell inequalities derived from combinatorics via triangular elimination
- Geometry of cuts and metrics
This page was built for publication: On the extension complexity of combinatorial polytopes
