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

Research

Links

Text available via DOI:

Keywords

View graph of relations

A new approach to the stable set problem based on ellipsoids

Research output: Contribution in Book/Report/Proceedings - With ISBN/ISSN › Chapter (peer-reviewed) › peer-review

Published

Standard

A new approach to the stable set problem based on ellipsoids. / Giandomenico, M; Letchford, A N; Rossi, F et al.
Integer Programming and Combinatorial Optimization : Proceedings of the 15th International IPCO Conference. ed. / Oktay Günlük; Gerhard Woeginger. Berlin: Springer, 2011. p. 223-234 (Lecture Notes in Computer Science; Vol. 6655).

Research output: Contribution in Book/Report/Proceedings - With ISBN/ISSN › Chapter (peer-reviewed) › peer-review

Harvard

Giandomenico, M, Letchford, AN, Rossi, F & Smriglio, S 2011, A new approach to the stable set problem based on ellipsoids. in O Günlük & G Woeginger (eds), Integer Programming and Combinatorial Optimization : Proceedings of the 15th International IPCO Conference. Lecture Notes in Computer Science, vol. 6655, Springer, Berlin, pp. 223-234, 15th International Conference, IPCO 2011, New York, United States, 15/06/11. https://doi.org/10.1007/978-3-642-20807-2_18

APA

Giandomenico, M., Letchford, A. N., Rossi, F., & Smriglio, S. (2011). A new approach to the stable set problem based on ellipsoids. In O. Günlük, & G. Woeginger (Eds.), Integer Programming and Combinatorial Optimization : Proceedings of the 15th International IPCO Conference (pp. 223-234). (Lecture Notes in Computer Science; Vol. 6655). Springer. https://doi.org/10.1007/978-3-642-20807-2_18

Vancouver

Giandomenico M, Letchford AN, Rossi F, Smriglio S. A new approach to the stable set problem based on ellipsoids. In Günlük O, Woeginger G, editors, Integer Programming and Combinatorial Optimization : Proceedings of the 15th International IPCO Conference. Berlin: Springer. 2011. p. 223-234. (Lecture Notes in Computer Science). doi: 10.1007/978-3-642-20807-2_18

Author

Giandomenico, M ; Letchford, A N ; Rossi, F et al. / A new approach to the stable set problem based on ellipsoids. Integer Programming and Combinatorial Optimization : Proceedings of the 15th International IPCO Conference. editor / Oktay Günlük ; Gerhard Woeginger. Berlin : Springer, 2011. pp. 223-234 (Lecture Notes in Computer Science).

Bibtex

@inbook{8033947dd8004dd6a2ea51ef68c1902b,
title = "A new approach to the stable set problem based on ellipsoids",
abstract = "A new exact approach to the stable set problem is presented, which attempts to avoids 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 is then used to derive cutting planes, which can be used within a linear programming-based branch-and-cut algorithm. Preliminary computational results indicate that the cutting planes are strong and easy to generate.",
keywords = "stable set problem, semidefinite programming, combinatorial optimisation",
author = "M Giandomenico and Letchford, {A N} and F Rossi and S Smriglio",
year = "2011",
doi = "10.1007/978-3-642-20807-2_18",
language = "English",
isbn = "9783642208065",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "223--234",
editor = "Oktay G{\"u}nl{\"u}k and Gerhard Woeginger",
booktitle = "Integer Programming and Combinatorial Optimization",
note = "15th International Conference, IPCO 2011 ; Conference date: 15-06-2011 Through 17-06-2011",

}

RIS

TY - CHAP

T1 - A new approach to the stable set problem based on ellipsoids

AU - Giandomenico, M

AU - Letchford, A N

AU - Rossi, F

AU - Smriglio, S

PY - 2011

Y1 - 2011

N2 - A new exact approach to the stable set problem is presented, which attempts to avoids 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 is then used to derive cutting planes, which can be used within a linear programming-based branch-and-cut algorithm. Preliminary computational results indicate that the cutting planes are strong and easy to generate.

AB - A new exact approach to the stable set problem is presented, which attempts to avoids 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 is then used to derive cutting planes, which can be used within a linear programming-based branch-and-cut algorithm. Preliminary computational results indicate that the cutting planes are strong and easy to generate.

KW - stable set problem

KW - semidefinite programming

KW - combinatorial optimisation

U2 - 10.1007/978-3-642-20807-2_18

DO - 10.1007/978-3-642-20807-2_18

M3 - Chapter (peer-reviewed)

SN - 9783642208065

T3 - Lecture Notes in Computer Science

SP - 223

EP - 234

BT - Integer Programming and Combinatorial Optimization

A2 - Günlük, Oktay

A2 - Woeginger, Gerhard

PB - Springer

CY - Berlin

T2 - 15th International Conference, IPCO 2011

Y2 - 15 June 2011 through 17 June 2011

ER -