Strong reductions for extended formulations
From MaRDI portal
Publication:1801022
DOI10.1007/s10107-018-1316-yzbMath1411.90211arXiv1512.04932OpenAlexW2888663778MaRDI QIDQ1801022
Sebastian Pokutta, Gábor Braun, Aurko Roy
Publication date: 26 October 2018
Published in: Mathematical Programming. Series A. Series B, Integer Programming and Combinatorial Optimization (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1512.04932
Semidefinite programming (90C22) Fractional programming (90C32) Linear programming (90C05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
Affine reductions for LPs and SDPs ⋮ Limitations of semidefinite programs for separable states and entangled games ⋮ LP Formulations for Polynomial Optimization Problems ⋮ A tight approximation algorithm for the cluster vertex deletion problem ⋮ No Small Linear Program Approximates Vertex Cover Within a Factor 2 − ɛ ⋮ New limits of treewidth-based tractability in optimization
Cites Work
- Expressing combinatorial optimization problems by linear programs
- The stable set problem and the lift-and-project ranks of graphs
- On the hardness of approximating Multicut and Sparsest-Cut
- On a Representation of the Matching Polytope Via Semidefinite Liftings
- Inapproximability of Combinatorial Problems via Small LPs and SDPs
- Lower Bounds on the Size of Semidefinite Programming Relaxations
- Complexity Analyses of Bienstock–Zuckerberg and Lasserre Relaxations on the Matching and Stable Set Polytopes
- Approximate Constraint Satisfaction Requires Large LP Relaxations
- Approximation Limits of Linear Programs (Beyond Hierarchies)
- Gadgets, Approximation, and Linear Programming
- The Matching Polytope has Exponential Extension Complexity
- Approximating rectangles by juntas and weakly-exponential lower bounds for LP relaxations of CSPs
- Optimal Long Code Test with One Free Bit
- A $(\log n)^{\Omega(1)}$ Integrality Gap for the Sparsest Cut SDP
- Integrality gaps for Sherali-Adams relaxations
- CSP gaps and reductions in the lasserre hierarchy
- Extension Complexity, MSO Logic, and Treewidth
- Linear vs. semidefinite extended formulations
- Euclidean distortion and the sparsest cut
- Sparsest cut on bounded treewidth graphs
- The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative-Type Metrics into ℓ 1
