Unification of lower-bound analyses of the lift-and-project rank of combinatorial optimization polyhedra
From MaRDI portal
Publication:2462348
DOI10.1016/j.dam.2007.07.021zbMath1152.90538OpenAlexW2127943911MaRDI QIDQ2462348
Publication date: 30 November 2007
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2007.07.021
Related Items (7)
Introduction to Donaldson–Thomas and Stable Pair Invariants ⋮ Handelman rank of zero-diagonal quadratic programs over a hypercube and its applications ⋮ Rank of Handelman hierarchy for Max-Cut ⋮ Sum-of-squares hierarchy lower bounds for symmetric formulations ⋮ Rank bounds for a hierarchy of Lovász and Schrijver ⋮ Complexity Analyses of Bienstock–Zuckerberg and Lasserre Relaxations on the Matching and Stable Set Polytopes ⋮ A Comprehensive Analysis of Polyhedral Lift-and-Project Methods
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On cutting-plane proofs in combinatorial optimization
- A reformulation-linearization technique for solving discrete and continuous nonconvex problems
- Disjunctive programming: Properties of the convex hull of feasible points
- Bounds on the Chvatal rank of polytopes in the 0/1-cube
- 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
- Semidefinite programs and association schemes
- A lift-and-project cutting plane algorithm for mixed 0-1 programs
- Tree-width and the Sherali-Adams operator
- An interrelation between line graphs, eigenvalues, and matroids
- On a Representation of the Matching Polytope Via Semidefinite Liftings
- On the Matrix-Cut Rank of Polyhedra
- Polynomials nonnegative on a grid and discrete optimization
- Tighter Linear and Semidefinite Relaxations for Max-Cut Based on the Lovász--Schrijver Lift-and-Project Procedure
- A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
- Cones of Matrices and Set-Functions and 0–1 Optimization
- Cones of Matrices and Successive Convex Relaxations of Nonconvex Sets
- Subset Algebra Lift Operators for 0-1 Integer Programming
- The Probable Value of the Lovász--Schrijver Relaxations for Maximum Independent Set
- On Lovász--Schrijver Lift-and-Project Procedures on the Dantzig--Fulkerson--Johnson Relaxation of the TSP
- Lectures on matroids
- When Does the Positive Semidefiniteness Constraint Help in Lifting Procedures?
- Lower Bound for the Number of Iterations in Semidefinite Hierarchies for the Cut Polytope
This page was built for publication: Unification of lower-bound analyses of the lift-and-project rank of combinatorial optimization polyhedra
