S-Space College of Engineering/Engineering Practice School (공과대학/대학원) Dept. of Industrial Engineering (산업공학과) Journal Papers (저널논문_산업공학과)
Unification of lower-bound analyses of the lift-and-project rank of combinatorial optimization polyhedra
- Hong, Sung-Pil; Tuncel, Levent
- Issue Date
- Discrete Appl. Math. 156 (2008) 25-41
- We present a unifying framework to establish a lower bound on the number of semidefinite-programming-based lift-and-project
iterations (rank) for computing the convex hull of the feasible solutions of various combinatorial optimization problems. This
framework is based on the maps which are commutative with the lift-and-project operators. Some special commutative maps were
originally observed by Lovász and Schrijver and have been used usually implicitly in the previous lower-bound analyses. In this
paper, we formalize the lift-and-project commutative maps and propose a general framework for lower-bound analysis, in which we
can recapture many of the previous lower-bound results on the lift-and-project ranks.
- Files in This Item: There are no files associated with this item.