On the polyhedral lift-and-project methods and the fractional stable set polytope |
| |
Authors: | Yu-Hin Au Levent Tunçel |
| |
Affiliation: | Department of Combinatorics and Optimization, Faculty of Mathematics, University of Waterloo, Waterloo, Ontario, N2L 3G1, Canada |
| |
Abstract: | We study two polyhedral lift-and-project operators (originally proposed by Lovász and Schrijver in 1991) applied to the fractional stable set polytopes. First, we provide characterizations of all valid inequalities generated by these operators. Then, we present some seven-node graphs on which the operator enforcing the symmetry of the matrix variable is strictly stronger on the odd-cycle polytope of these graphs than the operator without this symmetry requirement. This disproves a conjecture of Lipták and Tunçel from 2003. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|