Strong reductions for extended formulations

DOI10.1007/978-3-319-33461-5_29zbMATH Open1411.90211arXiv1512.04932OpenAlexW2888663778MaRDI QIDQ1801022FDOQ1801022

Authors: Gábor Braun, Sebastian Pokutta, 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

Recommendations

• Strong reductions for extended formulations
• Affine reductions for LPs and SDPs
• Linear vs. semidefinite extended formulations
• Inapproximability of combinatorial problems via small LPs and SDPs
• CSP gaps and reductions in the lasserre hierarchy

zbMATH Keywords

reductionsextended formulationmax cutone free bitsparsest cuts

Mathematics Subject Classification ID

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

Cites Work

• Expressing combinatorial optimization problems by linear programs
• Gadgets, Approximation, and Linear Programming
• A $(\log n)^{\Omega(1)}$ Integrality Gap for the Sparsest Cut SDP
• Linear vs. semidefinite extended formulations
• On the hardness of approximating Multicut and Sparsest-Cut
• The Matching Polytope has Exponential Extension Complexity
• The stable set problem and the lift-and-project ranks of graphs
• Approximate Constraint Satisfaction Requires Large LP Relaxations
• Approximation Limits of Linear Programs (Beyond Hierarchies)
• Integrality gaps for Sherali-Adams relaxations
• Complexity analyses of Bienstock-Zuckerberg and lasserre relaxations on the matching and stable set polytopes
• Euclidean distortion and the sparsest cut
• Inapproximability of combinatorial problems via small LPs and SDPs
• Lower bounds on the size of semidefinite programming relaxations
• On a representation of the matching polytope via semidefinite liftings
• Optimal Long Code Test with One Free Bit
• Extension complexity, MSO logic, and treewidth
• The unique games conjecture, integrality gap for cut problems and embeddability of negative-type metrics into \(\ell_1\)
• CSP gaps and reductions in the lasserre hierarchy
• Sparsest cut on bounded treewidth graphs: algorithms and hardness results
• Approximating rectangles by juntas and weakly-exponential lower bounds for LP relaxations of CSPs

Cited In (9)

• Strong reductions for extended formulations
• Limitations of semidefinite programs for separable states and entangled games
• A tight approximation algorithm for the cluster vertex deletion problem
• Solving LP relaxations of some NP-hard problems is as hard as solving any linear program
• LP relaxations of some NP-hard problems are as hard as any LP
• LP formulations for polynomial optimization problems
• No small linear program approximates vertex cover within a factor \(2 -\varepsilon\)
• New limits of treewidth-based tractability in optimization
• Affine reductions for LPs and SDPs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1801022)