Home > Research > Publications & Outputs > Complexity results for the gap inequalities for...

Research

Links

Text available via DOI:

Keywords

View graph of relations

Complexity results for the gap inequalities for the max-cut problem

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

Published

Standard

Complexity results for the gap inequalities for the max-cut problem. / Galli, Laura; Kaparis, Konstantinos; Letchford, A N.
In: Operations Research Letters, Vol. 40, No. 3, 05.2012, p. 149-152.

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

Harvard

Galli, L, Kaparis, K & Letchford, AN 2012, 'Complexity results for the gap inequalities for the max-cut problem', Operations Research Letters, vol. 40, no. 3, pp. 149-152. https://doi.org/10.1016/j.orl.2012.01.010

APA

Galli, L., Kaparis, K., & Letchford, A. N. (2012). Complexity results for the gap inequalities for the max-cut problem. Operations Research Letters, 40(3), 149-152. https://doi.org/10.1016/j.orl.2012.01.010

Vancouver

Galli L, Kaparis K, Letchford AN. Complexity results for the gap inequalities for the max-cut problem. Operations Research Letters. 2012 May;40(3):149-152. doi: 10.1016/j.orl.2012.01.010

Author

Galli, Laura ; Kaparis, Konstantinos ; Letchford, A N. / Complexity results for the gap inequalities for the max-cut problem. In: Operations Research Letters. 2012 ; Vol. 40, No. 3. pp. 149-152.

Bibtex

@article{a9fe63fd1a954549b283d22aed5cc866,
title = "Complexity results for the gap inequalities for the max-cut problem",
abstract = "We prove several complexity results about the gap inequalities for the max-cut problem, including (i) the gap-1 inequalities do not imply the other gap inequalities, unless NP=Co NP; (ii) there must exist non-redundant gap inequalities with exponentially large coefficients, unless NP=Co NP; (iii) the associated separation problem can be solved in finite (doubly exponential) time.",
keywords = "computational complexity, max-cut problem, cutting planes",
author = "Laura Galli and Konstantinos Kaparis and Letchford, {A N}",
note = "This is the 2nd of two papers on {"}gap inequalities{"}. The other, already published in OR Letters in 2011, was entitled {"} Gap inequalities for non-convex mixed-integer quadratic programs{"}.",
year = "2012",
month = may,
doi = "10.1016/j.orl.2012.01.010",
language = "English",
volume = "40",
pages = "149--152",
journal = "Operations Research Letters",
issn = "0167-6377",
publisher = "Elsevier",
number = "3",

}

RIS

TY - JOUR

T1 - Complexity results for the gap inequalities for the max-cut problem

AU - Galli, Laura

AU - Kaparis, Konstantinos

AU - Letchford, A N

N1 - This is the 2nd of two papers on "gap inequalities". The other, already published in OR Letters in 2011, was entitled " Gap inequalities for non-convex mixed-integer quadratic programs".

PY - 2012/5

Y1 - 2012/5

N2 - We prove several complexity results about the gap inequalities for the max-cut problem, including (i) the gap-1 inequalities do not imply the other gap inequalities, unless NP=Co NP; (ii) there must exist non-redundant gap inequalities with exponentially large coefficients, unless NP=Co NP; (iii) the associated separation problem can be solved in finite (doubly exponential) time.

AB - We prove several complexity results about the gap inequalities for the max-cut problem, including (i) the gap-1 inequalities do not imply the other gap inequalities, unless NP=Co NP; (ii) there must exist non-redundant gap inequalities with exponentially large coefficients, unless NP=Co NP; (iii) the associated separation problem can be solved in finite (doubly exponential) time.

KW - computational complexity

KW - max-cut problem

KW - cutting planes

U2 - 10.1016/j.orl.2012.01.010

DO - 10.1016/j.orl.2012.01.010

M3 - Journal article

VL - 40

SP - 149

EP - 152

JO - Operations Research Letters

JF - Operations Research Letters

SN - 0167-6377

IS - 3

ER -