Home > Research > Publications & Outputs > On the Lovász theta function and some variants

Research

Associated organisational units

Electronic data

  • theta-function

    Rights statement: This is the author’s version of a work that was accepted for publication in Discrete Optimization. Changes resulting from the publishing process, such as peer review, editing, corrections, structural formatting, and other quality control mechanisms may not be reflected in this document. Changes may have been made to this work since it was submitted for publication. A definitive version was subsequently published in Discrete Optimization, 25, 2017 DOI: 10.1016/d.disopt.2017.04.001

    Accepted author manuscript, 354 KB, PDF document

    Available under license: CC BY-NC-ND: Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License

Links

Text available via DOI:

Keywords

View graph of relations

On the Lovász theta function and some variants

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

Published

Standard

On the Lovász theta function and some variants. / Galli, Laura; Letchford, Adam Nicholas.
In: Discrete Optimization, Vol. 25, 27.07.2017, p. 159-174.

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

Harvard

Galli, L & Letchford, AN 2017, 'On the Lovász theta function and some variants', Discrete Optimization, vol. 25, pp. 159-174. https://doi.org/10.1016/j.disopt.2017.04.001

APA

Galli, L., & Letchford, A. N. (2017). On the Lovász theta function and some variants. Discrete Optimization, 25, 159-174. https://doi.org/10.1016/j.disopt.2017.04.001

Vancouver

Galli L, Letchford AN. On the Lovász theta function and some variants. Discrete Optimization. 2017 Jul 27;25:159-174. Epub 2017 May 13. doi: 10.1016/j.disopt.2017.04.001

Author

Galli, Laura ; Letchford, Adam Nicholas. / On the Lovász theta function and some variants. In: Discrete Optimization. 2017 ; Vol. 25. pp. 159-174.

Bibtex

@article{e9ee65e37bdf40148cf7da4dcd679d76,
title = "On the Lov{\'a}sz theta function and some variants",
abstract = "The Lov{\'a}sz theta function of a graph is a well-known upper bound on the stability number. It can be computed efficiently by solving a semidefinite program (SDP). Actually, one can solve either of two SDPs, one due to Lov{\'a}sz and the other to Gr{\"o}tschel et al. The former SDP is often thought to be preferable computationally, since it has fewer variables and constraints. We derive some new results on these two equivalent SDPs. The surprising result is that, if we weaken the SDPs by aggregating constraints, or strengthen them by adding cutting planes, the equivalence breaks down. In particular, the Gr{\"o}tschel et al. scheme typically yields a stronger bound than the Lov{\'a}sz one.",
keywords = "combinatorial optimisation, stable set problem, semidefinite programming",
author = "Laura Galli and Letchford, {Adam Nicholas}",
note = "This is the author{\textquoteright}s version of a work that was accepted for publication in Discrete Optimization. Changes resulting from the publishing process, such as peer review, editing, corrections, structural formatting, and other quality control mechanisms may not be reflected in this document. Changes may have been made to this work since it was submitted for publication. A definitive version was subsequently published in Discrete Optimization, 25, 2017 DOI: 10.1016/d.disopt.2017.04.001",
year = "2017",
month = jul,
day = "27",
doi = "10.1016/j.disopt.2017.04.001",
language = "English",
volume = "25",
pages = "159--174",
journal = "Discrete Optimization",
issn = "1572-5286",
publisher = "Elsevier",

}

RIS

TY - JOUR

T1 - On the Lovász theta function and some variants

AU - Galli, Laura

AU - Letchford, Adam Nicholas

N1 - This is the author’s version of a work that was accepted for publication in Discrete Optimization. Changes resulting from the publishing process, such as peer review, editing, corrections, structural formatting, and other quality control mechanisms may not be reflected in this document. Changes may have been made to this work since it was submitted for publication. A definitive version was subsequently published in Discrete Optimization, 25, 2017 DOI: 10.1016/d.disopt.2017.04.001

PY - 2017/7/27

Y1 - 2017/7/27

N2 - The Lovász theta function of a graph is a well-known upper bound on the stability number. It can be computed efficiently by solving a semidefinite program (SDP). Actually, one can solve either of two SDPs, one due to Lovász and the other to Grötschel et al. The former SDP is often thought to be preferable computationally, since it has fewer variables and constraints. We derive some new results on these two equivalent SDPs. The surprising result is that, if we weaken the SDPs by aggregating constraints, or strengthen them by adding cutting planes, the equivalence breaks down. In particular, the Grötschel et al. scheme typically yields a stronger bound than the Lovász one.

AB - The Lovász theta function of a graph is a well-known upper bound on the stability number. It can be computed efficiently by solving a semidefinite program (SDP). Actually, one can solve either of two SDPs, one due to Lovász and the other to Grötschel et al. The former SDP is often thought to be preferable computationally, since it has fewer variables and constraints. We derive some new results on these two equivalent SDPs. The surprising result is that, if we weaken the SDPs by aggregating constraints, or strengthen them by adding cutting planes, the equivalence breaks down. In particular, the Grötschel et al. scheme typically yields a stronger bound than the Lovász one.

KW - combinatorial optimisation

KW - stable set problem

KW - semidefinite programming

U2 - 10.1016/j.disopt.2017.04.001

DO - 10.1016/j.disopt.2017.04.001

M3 - Journal article

VL - 25

SP - 159

EP - 174

JO - Discrete Optimization

JF - Discrete Optimization

SN - 1572-5286

ER -