Publications
Detailed Information
Unification of lower-bound analyses of the lift-and-project rank of combinatorial optimization polyhedra
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Hong, Sung-Pil | - |
dc.contributor.author | Tuncel, Levent | - |
dc.date.accessioned | 2009-07-08T06:15:11Z | - |
dc.date.available | 2009-07-08T06:15:11Z | - |
dc.date.issued | 2007-09-14 | - |
dc.identifier.citation | Discrete Appl. Math. 156 (2008) 25-41 | en |
dc.identifier.issn | 0166-218X | - |
dc.identifier.uri | https://hdl.handle.net/10371/5334 | - |
dc.description.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. | en |
dc.language.iso | en | - |
dc.publisher | Elsevier | en |
dc.subject | Lift-and-project | en |
dc.subject | Semidefinite lifting | en |
dc.subject | Semidefinite programming | en |
dc.subject | Integer programming | en |
dc.title | Unification of lower-bound analyses of the lift-and-project rank of combinatorial optimization polyhedra | en |
dc.type | Article | en |
dc.contributor.AlternativeAuthor | 홍성필 | - |
dc.identifier.doi | 10.1016/j.dam.2007.07.021 | - |
dc.identifier.doi | 10.1016/j.dam.2007.07.021 | - |
dc.citation.journaltitle | Discrete Applied Mathematics | - |
- Appears in Collections:
- Files in This Item:
- There are no files associated with this item.
Item View & Download Count
Items in S-Space are protected by copyright, with all rights reserved, unless otherwise indicated.