SHERP

Unification of lower-bound analyses of the lift-and-project rank of combinatorial optimization polyhedra

Cited 0 time in webofscience Cited 0 time in scopus
Authors
Hong, Sung-Pil; Tuncel, Levent
Issue Date
2007-09-14
Publisher
Elsevier
Citation
Discrete Appl. Math. 156 (2008) 25-41
Keywords
Lift-and-project; Semidefinite lifting; Semidefinite programming; Integer programming
Abstract
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.
ISSN
0166-218X
Language
English
URI
http://hdl.handle.net/10371/5334
DOI
https://doi.org/10.1016/j.dam.2007.07.021
https://doi.org/10.1016/j.dam.2007.07.021
Files in This Item:
There are no files associated with this item.
Appears in Collections:
College of Engineering/Engineering Practice School (공과대학/대학원)Dept. of Industrial Engineering (산업공학과)Journal Papers (저널논문_산업공학과)
  • mendeley

Items in S-Space are protected by copyright, with all rights reserved, unless otherwise indicated.

Browse