Average case polyhedral complexity of the maximum stable set problem
From MaRDI portal
Publication:344955
DOI10.1007/s10107-016-0989-3zbMath1350.05152arXiv1311.4001OpenAlexW1832679686MaRDI QIDQ344955
Samuel Fiorini, Sebastian Pokutta, Gábor Braun
Publication date: 25 November 2016
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1311.4001
Related Items (4)
Affine reductions for LPs and SDPs ⋮ A note on “A linear‐size zero‐one programming model for the minimum spanning tree problem in planar graphs” ⋮ Exponential Lower Bounds for Polytopes in Combinatorial Optimization ⋮ New limits of treewidth-based tractability in optimization
Cites Work
- Unnamed Item
- Common information and unique disjointness
- On the extension complexity of combinatorial polytopes
- Expressing combinatorial optimization problems by linear programs
- On the distributional complexity of disjointness
- A short proof that the extension complexity of the correlation polytope grows exponentially
- Some \(0/1\) polytopes need exponential size extended formulations
- A note on the extension complexity of the knapsack polytope
- A linear-size zero?one programming model for the minimum spanning tree problem in planar graphs
- Exponential Lower Bounds for Polytopes in Combinatorial Optimization
- Inapproximability of Combinatorial Problems via Small LPs and SDPs
- Lower Bounds on the Size of Semidefinite Programming Relaxations
- Approximate Constraint Satisfaction Requires Large LP Relaxations
- Approximation Limits of Linear Programs (Beyond Hierarchies)
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- The Matching Polytope has Exponential Extension Complexity
- Nondeterministic Quantum Query and Communication Complexities
- The matching polytope does not admit fully-polynomial size relaxation schemes
- Linear vs. semidefinite extended formulations
- An information complexity approach to extended formulations
- Maximum matching and a polyhedron with 0,1-vertices
- Extended formulations in combinatorial optimization
This page was built for publication: Average case polyhedral complexity of the maximum stable set problem
