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

zbMATH Keywords

reductionsextended formulationmax cutone free bitsparsest cuts

Mathematics Subject Classification ID

Semidefinite programming (90C22) Fractional programming (90C32) Linear programming (90C05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (6)

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

This page was built for publication: Strong reductions for extended formulations