On the extension complexity of combinatorial polytopes

DOI10.1007/s10107-014-0764-2zbMath1336.90095arXiv1302.2340OpenAlexW1942134738MaRDI QIDQ745682

David Avis, Hans Raj Tiwary

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

zbMATH Keywords

cut polytopegraph minorsextension complexity

Mathematics Subject Classification ID

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