Strong reductions for extended formulations

DOI10.1007/978-3-319-33461-5_29zbMath1411.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)

Abstract: We generalize the reduction mechanism for linear programming problems and semidefinite programming problems from [arXiv:1410.8816] in two ways 1) relaxing the requirement of affineness and 2) extending to fractional optimization problems. As applications we provide several new LP-hardness and SDP-hardness results, e.g., for the SparsestCut problem, the BalancedSeparator problem, the MaxCut problem and the Matching problem on 3-regular graphs. We also provide a new, very strong Lasserre integrality gap result for the IndependentSet problem, which is strictly greater than the best known LP approximation, showing that the Lasserre hierarchy does not always provide the tightest SDP relaxation.

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)

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

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

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