Lift-and-project ranks and antiblocker duality

DOI10.1016/j.orl.2004.05.002zbMath1076.90035OpenAlexW2089152151MaRDI QIDQ1886795

László Lipták, Tunçel, Levent

Publication date: 19 November 2004

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.orl.2004.05.002

zbMATH Keywords

Lift-and-projectStable set problem

Mathematics Subject Classification ID

Semidefinite programming (90C22) Integer programming (90C10) Combinatorial optimization (90C27) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (2)

Comparing Imperfection Ratio and Imperfection Index for Graph Classes ⋮ An axiomatic duality framework for the theta body and related convex corners

Cites Work

• Unnamed Item
• Geometric algorithms and combinatorial optimization
• On certain polytopes associated with graphs
• Lift-and-project cuts and perfect graphs
• The stable set problem and the lift-and-project ranks of graphs
• The disjunctive procedure and blocker duality
• A lift-and-project cutting plane algorithm for mixed 0-1 programs
• Anti-blocking polyhedra
• Normal hypergraphs and the perfect graph conjecture
• 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
• Subset Algebra Lift Operators for 0-1 Integer Programming
• Blocking and anti-blocking pairs of polyhedra
• A Generalization of the Perfect Graph Theorem Under the Disjunctive Index
• Note On: N. E. Aguilera, M. S. Escalante, G. L. Nasini, “A Generalization of the Perfect Graph Theorem Under the Disjunctive Index”

This page was built for publication: Lift-and-project ranks and antiblocker duality