Unification of lower-bound analyses of the lift-and-project rank of combinatorial optimization polyhedra |
| |
Authors: | Sung-Pil Hong |
| |
Institution: | a Department of Industrial Engineering, Seoul National University, Seoul 151-744, South Korea b Department of Combinatorics and Optimization, Faculty of Mathematics, University of Waterloo, Waterloo, Ont., Canada N2L 3G1 |
| |
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. |
| |
Keywords: | 90C10 90C22 90C27 47D20 |
本文献已被 ScienceDirect 等数据库收录! |
|