A Comprehensive Analysis of Polyhedral Lift-and-Project Methods
From MaRDI portal
Publication:2790405
DOI10.1137/130950173zbMath1332.90219arXiv1312.5972OpenAlexW2963362520MaRDI QIDQ2790405
Tunçel, Levent, Yu Hin (Gary) Au
Publication date: 4 March 2016
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1312.5972
integer programmingsemidefinite programmingcombinatorial optimizationconvex relaxationslift-and-project methodsdesign and analysis of algorithms with discrete structures
Semidefinite programming (90C22) Integer programming (90C10) Combinatorial optimization (90C27) Set-valued operators (47H04) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Related Items (7)
Theoretical challenges towards cutting-plane selection ⋮ Elementary polytopes with high lift-and-project ranks for strong positive semidefinite operators ⋮ A Repeated Route-then-Schedule Approach to Coordinated Vehicle Platooning: Algorithms, Valid Inequalities and Computation ⋮ Circular (Yet Sound) Proofs in Propositional Logic ⋮ Lift \& project systems performing on the partial-vertex-cover polytope ⋮ Lift-and-project methods for set cover and knapsack ⋮ High Degree Sum of Squares Proofs, Bienstock--Zuckerberg Hierarchy, and Chvátal--Gomory Cuts
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Smallest compact formulation for the permutahedron
- Reduction of symmetric semidefinite programs using the regular \(\ast\)-representation
- Semidefinite bounds for the stability number of a graph via sums of squares of polynomials
- Expressing combinatorial optimization problems by linear programs
- Lift and project relaxations for the matching and related polytopes
- The stable set problem and the lift-and-project ranks of graphs
- Symmetry groups, semidefinite programs, and sums of squares
- Tighter representations for set partitioning problems
- A lift-and-project cutting plane algorithm for mixed 0-1 programs
- Unification of lower-bound analyses of the lift-and-project rank of combinatorial optimization polyhedra
- On a Representation of the Matching Polytope Via Semidefinite Liftings
- On the Matrix-Cut Rank of Polyhedra
- Tighter Linear and Semidefinite Relaxations for Max-Cut Based on the Lovász--Schrijver Lift-and-Project Procedure
- Approximation of the Stability Number of a Graph via Copositive Programming
- Perturbed sums-of-squares theorem for polynomial optimization and its applications
- Tight Gaps for Vertex Cover in the Sherali-Adams SDP Hierarchy
- Complexity Analyses of Bienstock–Zuckerberg and Lasserre Relaxations on the Matching and Stable Set Polytopes
- Integrality Gaps of Linear and Semi-Definite Programming Relaxations for Knapsack
- Approximate Constraint Satisfaction Requires Large LP Relaxations
- A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
- Improved Approximation Guarantees through Higher Levels of SDP Hierarchies
- Extending SDP Integrality Gaps to Sherali-Adams with Applications to Quadratic Programming and MaxCutGain
- A comparison of the Delsarte and Lovász bounds
- Cones of Matrices and Set-Functions and 0–1 Optimization
- On the Shannon capacity of a graph
- The Matching Polytope has Exponential Extension Complexity
- Subset Algebra Lift Operators for 0-1 Integer Programming
- Integrality gaps for Sherali-Adams relaxations
- Sherali-adams relaxations of the matching polytope
- CSP gaps and reductions in the lasserre hierarchy
- On Integrality Ratios for Asymmetric TSP in the Sherali-Adams Hierarchy
- Paths, Trees, and Flowers
- Computation of the Lasserre Ranks of Some Polytopes
- Integrality Gaps of $2-o(1)$ for Vertex Cover SDPs in the Lovász–Schrijver Hierarchy
- Linear vs. semidefinite extended formulations
- Linear Programming Hierarchies Suffice for Directed Steiner Tree
- Computing the Stability Number of a Graph Via Linear and Semidefinite Programming
- On Lovász--Schrijver Lift-and-Project Procedures on the Dantzig--Fulkerson--Johnson Relaxation of the TSP
- Improved Bounds for the Crossing Numbers of Km,n and Kn
- Sparsest cut on bounded treewidth graphs
- When Does the Positive Semidefiniteness Constraint Help in Lifting Procedures?
- A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming
This page was built for publication: A Comprehensive Analysis of Polyhedral Lift-and-Project Methods
