Home > Research > Publications & Outputs > An application of the Lovasz-Schrijver M(K,K) o...
View graph of relations

An application of the Lovasz-Schrijver M(K,K) operator to the stable set problem

Research output: Contribution to Journal/MagazineJournal articlepeer-review

Published

Standard

An application of the Lovasz-Schrijver M(K,K) operator to the stable set problem. / Giandomenico, M; Letchford, A N; Rossi, F et al.
In: Mathematical Programming, Vol. 120, No. 2, 2009, p. 381-401.

Research output: Contribution to Journal/MagazineJournal articlepeer-review

Harvard

Giandomenico, M, Letchford, AN, Rossi, F & Smriglio, S 2009, 'An application of the Lovasz-Schrijver M(K,K) operator to the stable set problem', Mathematical Programming, vol. 120, no. 2, pp. 381-401. https://doi.org/10.1007/s10107-008-0219-8

APA

Giandomenico, M., Letchford, A. N., Rossi, F., & Smriglio, S. (2009). An application of the Lovasz-Schrijver M(K,K) operator to the stable set problem. Mathematical Programming, 120(2), 381-401. https://doi.org/10.1007/s10107-008-0219-8

Vancouver

Giandomenico M, Letchford AN, Rossi F, Smriglio S. An application of the Lovasz-Schrijver M(K,K) operator to the stable set problem. Mathematical Programming. 2009;120(2):381-401. doi: 10.1007/s10107-008-0219-8

Author

Giandomenico, M ; Letchford, A N ; Rossi, F et al. / An application of the Lovasz-Schrijver M(K,K) operator to the stable set problem. In: Mathematical Programming. 2009 ; Vol. 120, No. 2. pp. 381-401.

Bibtex

@article{3f2064cae0bf45a9b47339500955b8a3,
title = "An application of the Lovasz-Schrijver M(K,K) operator to the stable set problem",
abstract = "Although the lift-and-project operators of Lov{\'a}sz and Schrijver have been the subject of intense study, their M(K, K) operator has received little attention. We consider an application of this operator to the stable set problem. We begin with an initial linear programming (LP) relaxation consisting of clique and non-negativity inequalities, and then apply the operator to obtain a stronger extended LP relaxation. We discuss theoretical properties of the resulting relaxation, describe the issues that must be overcome to obtain an effective practical implementation, and give extensive computational results. Remarkably, the upper bounds obtained are sometimes stronger than those obtained with semidefinite programming techniques.",
keywords = "Lov{\'a}sz-Schrijver operators, stable set problem, semidefinite programming",
author = "M Giandomenico and Letchford, {A N} and F Rossi and S Smriglio",
year = "2009",
doi = "10.1007/s10107-008-0219-8",
language = "English",
volume = "120",
pages = "381--401",
journal = "Mathematical Programming",
issn = "0025-5610",
publisher = "Springer-Verlag GmbH and Co. KG",
number = "2",

}

RIS

TY - JOUR

T1 - An application of the Lovasz-Schrijver M(K,K) operator to the stable set problem

AU - Giandomenico, M

AU - Letchford, A N

AU - Rossi, F

AU - Smriglio, S

PY - 2009

Y1 - 2009

N2 - Although the lift-and-project operators of Lovász and Schrijver have been the subject of intense study, their M(K, K) operator has received little attention. We consider an application of this operator to the stable set problem. We begin with an initial linear programming (LP) relaxation consisting of clique and non-negativity inequalities, and then apply the operator to obtain a stronger extended LP relaxation. We discuss theoretical properties of the resulting relaxation, describe the issues that must be overcome to obtain an effective practical implementation, and give extensive computational results. Remarkably, the upper bounds obtained are sometimes stronger than those obtained with semidefinite programming techniques.

AB - Although the lift-and-project operators of Lovász and Schrijver have been the subject of intense study, their M(K, K) operator has received little attention. We consider an application of this operator to the stable set problem. We begin with an initial linear programming (LP) relaxation consisting of clique and non-negativity inequalities, and then apply the operator to obtain a stronger extended LP relaxation. We discuss theoretical properties of the resulting relaxation, describe the issues that must be overcome to obtain an effective practical implementation, and give extensive computational results. Remarkably, the upper bounds obtained are sometimes stronger than those obtained with semidefinite programming techniques.

KW - Lovász-Schrijver operators

KW - stable set problem

KW - semidefinite programming

U2 - 10.1007/s10107-008-0219-8

DO - 10.1007/s10107-008-0219-8

M3 - Journal article

VL - 120

SP - 381

EP - 401

JO - Mathematical Programming

JF - Mathematical Programming

SN - 0025-5610

IS - 2

ER -