Article ID: | iaor20051109 |
Country: | Germany |
Volume: | 98 |
Issue: | 1/3 |
Start Page Number: | 319 |
End Page Number: | 353 |
Publication Date: | Jan 2003 |
Journal: | Mathematical Programming |
Authors: | Tunel L., Liptk L. |
We study the lift-and-project procedures for solving combinatorial optimization problems, as described by Lovász and Schrijver, in the context of the stable set problem on graphs. We investigate how the procedures' performances change as we apply fundamental graph operations. We show that the odd subdivision of an edge and the subdivision of a star operations (as well as their common generalization, the stretching of a vertex operation) cannot decrease the