Home > Research > Publications & Outputs > Ellipsoidal relaxations of the stable set problem

Electronic data

  • ellipsoids-source

    Rights statement: Copyright © 2015, Society for Industrial and Applied Mathematics

    Accepted author manuscript, 368 KB, PDF document

    Available under license: CC BY: Creative Commons Attribution 4.0 International License

Links

Text available via DOI:

View graph of relations

Ellipsoidal relaxations of the stable set problem: theory and algorithms

Research output: Contribution to journalJournal article

Published
Close
<mark>Journal publication date</mark>1/08/2015
<mark>Journal</mark>SIAM Journal on Optimization
Issue number3
Volume25
Number of pages20
Pages (from-to)1944-1963
Publication statusPublished
Original languageEnglish

Abstract

A new exact approach to the stable set problem is presented, which attempts to avoid the pitfalls of existing approaches based on linear and semidefinite programming. The method begins by constructing an ellipsoid that contains the stable set polytope and has the property that the upper bound obtained by optimising over it is equal to the Lovasz theta number. This ellipsoid can then be used to construct useful convex relaxations of the stable set problem, which can be
embedded within a branch-and-bound framework. Extensive computational
results are given, which indicate the potential of the approach.

Bibliographic note

Copyright © 2015, Society for Industrial and Applied Mathematics