Strong reductions for extended formulations
Preprint
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.Keywords
All Related Versions
This publication has 16 references indexed in Scilit:
- A Comprehensive Analysis of Polyhedral Lift-and-Project MethodsSIAM Journal on Discrete Mathematics, 2016
- No Small Linear Program Approximates Vertex Cover within a Factor 2 -- e2015
- The matching polytope does not admit fully-polynomial size relaxation schemes2014
- Euclidean distortion and the sparsest cutJournal of the American Mathematical Society, 2007
- The stable set problem and the lift-and-project ranks of graphsMathematical Programming, 2003
- On cuts and matchings in planar graphsMathematical Programming, 1993
- Expressing combinatorial optimization problems by Linear ProgramsJournal of Computer and System Sciences, 1991
- Compact systems for T-join and perfect matching polyhedra of graphs with bounded genusOperations Research Letters, 1991
- A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming ProblemsSIAM Journal on Discrete Mathematics, 1990
- The monadic second-order logic of graphs. I. Recognizable sets of finite graphsInformation and Computation, 1990