We have over 12,000 students, from over 100 countries, within one of the safest campuses in the UK


93% of Lancaster students go into work or further study within six months of graduating

Home > Research > Publications & Outputs > A new approach to the stable set problem based ...
View graph of relations

« Back

A new approach to the stable set problem based on ellipsoids

Research output: Working paper


Publication date2011
Place of publicationLancaster University
PublisherThe Department of Management Science
Number of pages0
Original languageEnglish

Publication series

NameManagement Science Working Paper Series


We present a new exact approach to the stable set problem, which avoids the pitfalls of existing approaches based on linear and semidefinite programming. The main idea is to construct an ellipsoid which contains the stable set polytope, in such a way that the upper bound obtained by optimising over the ellipsoid is equal to the Lovasz theta number. This ellipsoid can then be used to construct useful convex programming relaxations of the stable set problem or, more interestingly, to derive cutting planes. These cutting planes turn out to be remarkably strong and easy to generate.

Bibliographic note

This was eventually published as: M. Giandomenico, A.N. Letchford, F. Rossi & S. Smriglio (2011) An new approach to the stable set problem based on ellipsoids. In O. Günlük & G.J. Woeginger (eds.) Integer Programming and Combinatorial Optimization XV. Lecture Notes in Computer Science, vol. 6655. Heidelberg: Springer.