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

Research

Associated organisational units

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:

Keywords

View graph of relations

Ellipsoidal relaxations of the stable set problem: theory and algorithms

Research output: Contribution to Journal/Magazine › Journal article › peer-review

Published

Standard

Ellipsoidal relaxations of the stable set problem: theory and algorithms. / Giandomenico, Monia; Letchford, Adam; Rossi, Fabrizio et al.
In: SIAM Journal on Optimization, Vol. 25, No. 3, 01.08.2015, p. 1944-1963.

Research output: Contribution to Journal/Magazine › Journal article › peer-review

Harvard

Giandomenico, M, Letchford, A, Rossi, F & Smriglio, S 2015, 'Ellipsoidal relaxations of the stable set problem: theory and algorithms', SIAM Journal on Optimization, vol. 25, no. 3, pp. 1944-1963. https://doi.org/10.1137/140966332

APA

Giandomenico, M., Letchford, A., Rossi, F., & Smriglio, S. (2015). Ellipsoidal relaxations of the stable set problem: theory and algorithms. SIAM Journal on Optimization, 25(3), 1944-1963. https://doi.org/10.1137/140966332

Vancouver

Giandomenico M, Letchford A, Rossi F, Smriglio S. Ellipsoidal relaxations of the stable set problem: theory and algorithms. SIAM Journal on Optimization. 2015 Aug 1;25(3):1944-1963. doi: 10.1137/140966332

Author

Giandomenico, Monia ; Letchford, Adam ; Rossi, Fabrizio et al. / Ellipsoidal relaxations of the stable set problem : theory and algorithms. In: SIAM Journal on Optimization. 2015 ; Vol. 25, No. 3. pp. 1944-1963.

Bibtex

@article{78b4f250a81f4f6fa60cc2f2155ec947,
title = "Ellipsoidal relaxations of the stable set problem: theory and algorithms",
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 beembedded within a branch-and-bound framework. Extensive computationalresults are given, which indicate the potential of the approach.",
keywords = "combinatorial optimisation, semidefinite programming, branch-and-cut",
author = "Monia Giandomenico and Adam Letchford and Fabrizio Rossi and Stefano Smriglio",
note = "Copyright {\textcopyright} 2015, Society for Industrial and Applied Mathematics",
year = "2015",
month = aug,
day = "1",
doi = "10.1137/140966332",
language = "English",
volume = "25",
pages = "1944--1963",
journal = "SIAM Journal on Optimization",
issn = "1052-6234",
publisher = "Society for Industrial and Applied Mathematics Publications",
number = "3",

}

RIS

TY - JOUR

T1 - Ellipsoidal relaxations of the stable set problem

T2 - theory and algorithms

AU - Giandomenico, Monia

AU - Letchford, Adam

AU - Rossi, Fabrizio

AU - Smriglio, Stefano

N1 - Copyright © 2015, Society for Industrial and Applied Mathematics

PY - 2015/8/1

Y1 - 2015/8/1

N2 - 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 beembedded within a branch-and-bound framework. Extensive computationalresults are given, which indicate the potential of the approach.

AB - 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 beembedded within a branch-and-bound framework. Extensive computationalresults are given, which indicate the potential of the approach.

KW - combinatorial optimisation

KW - semidefinite programming

KW - branch-and-cut

U2 - 10.1137/140966332

DO - 10.1137/140966332

M3 - Journal article

VL - 25

SP - 1944

EP - 1963

JO - SIAM Journal on Optimization

JF - SIAM Journal on Optimization

SN - 1052-6234

IS - 3

ER -