Home > Research > Publications & Outputs > Gap inequalities for the max-cut problem: a cut...

Links

Text available via DOI:

View graph of relations

Gap inequalities for the max-cut problem: a cutting-plane algorithm

Research output: Contribution in Book/Report/Proceedings - With ISBN/ISSNChapter (peer-reviewed)

Published

Standard

Gap inequalities for the max-cut problem: a cutting-plane algorithm. / Galli, Laura; Kaparis, Konstantinos; Letchford, Adam.

Combinatorial Optimization: Second International Symposium, ISCO 2012, Athens, Greece, April 19-21, 2012, Revised Selected Papers. ed. / A.R. Mahjoub. Berlin : Springer, 2012. p. 178-188 (Lecture Notes in Computer Science; Vol. 7422).

Research output: Contribution in Book/Report/Proceedings - With ISBN/ISSNChapter (peer-reviewed)

Harvard

Galli, L, Kaparis, K & Letchford, A 2012, Gap inequalities for the max-cut problem: a cutting-plane algorithm. in AR Mahjoub (ed.), Combinatorial Optimization: Second International Symposium, ISCO 2012, Athens, Greece, April 19-21, 2012, Revised Selected Papers. Lecture Notes in Computer Science, vol. 7422, Springer, Berlin, pp. 178-188. https://doi.org/10.1007/978-3-642-32147-4_17

APA

Galli, L., Kaparis, K., & Letchford, A. (2012). Gap inequalities for the max-cut problem: a cutting-plane algorithm. In A. R. Mahjoub (Ed.), Combinatorial Optimization: Second International Symposium, ISCO 2012, Athens, Greece, April 19-21, 2012, Revised Selected Papers (pp. 178-188). (Lecture Notes in Computer Science; Vol. 7422). Springer. https://doi.org/10.1007/978-3-642-32147-4_17

Vancouver

Galli L, Kaparis K, Letchford A. Gap inequalities for the max-cut problem: a cutting-plane algorithm. In Mahjoub AR, editor, Combinatorial Optimization: Second International Symposium, ISCO 2012, Athens, Greece, April 19-21, 2012, Revised Selected Papers. Berlin: Springer. 2012. p. 178-188. (Lecture Notes in Computer Science). https://doi.org/10.1007/978-3-642-32147-4_17

Author

Galli, Laura ; Kaparis, Konstantinos ; Letchford, Adam. / Gap inequalities for the max-cut problem: a cutting-plane algorithm. Combinatorial Optimization: Second International Symposium, ISCO 2012, Athens, Greece, April 19-21, 2012, Revised Selected Papers. editor / A.R. Mahjoub. Berlin : Springer, 2012. pp. 178-188 (Lecture Notes in Computer Science).

Bibtex

@inbook{55c0338e60e64d5584bd7b8e2e199df3,
title = "Gap inequalities for the max-cut problem: a cutting-plane algorithm",
abstract = "Laurent & Poljak introduced a class of valid inequalities for the max-cut problem, called gap inequalities, which include many other known inequalities as special cases. The gap inequalities have received little attention and are poorly understood. This paper presents the first ever computational results. In particular, we describe a cutting-plane scheme based on an effective heuristic separation algorithm for gap inequalities, and show that these yield extremely strong upper bounds in practice.",
keywords = "combinatorial optimisation, max-cut problem",
author = "Laura Galli and Konstantinos Kaparis and Adam Letchford",
year = "2012",
doi = "10.1007/978-3-642-32147-4_17",
language = "English",
isbn = "9783642321467",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "178--188",
editor = "A.R. Mahjoub",
booktitle = "Combinatorial Optimization",

}

RIS

TY - CHAP

T1 - Gap inequalities for the max-cut problem: a cutting-plane algorithm

AU - Galli, Laura

AU - Kaparis, Konstantinos

AU - Letchford, Adam

PY - 2012

Y1 - 2012

N2 - Laurent & Poljak introduced a class of valid inequalities for the max-cut problem, called gap inequalities, which include many other known inequalities as special cases. The gap inequalities have received little attention and are poorly understood. This paper presents the first ever computational results. In particular, we describe a cutting-plane scheme based on an effective heuristic separation algorithm for gap inequalities, and show that these yield extremely strong upper bounds in practice.

AB - Laurent & Poljak introduced a class of valid inequalities for the max-cut problem, called gap inequalities, which include many other known inequalities as special cases. The gap inequalities have received little attention and are poorly understood. This paper presents the first ever computational results. In particular, we describe a cutting-plane scheme based on an effective heuristic separation algorithm for gap inequalities, and show that these yield extremely strong upper bounds in practice.

KW - combinatorial optimisation

KW - max-cut problem

U2 - 10.1007/978-3-642-32147-4_17

DO - 10.1007/978-3-642-32147-4_17

M3 - Chapter (peer-reviewed)

SN - 9783642321467

T3 - Lecture Notes in Computer Science

SP - 178

EP - 188

BT - Combinatorial Optimization

A2 - Mahjoub, A.R.

PB - Springer

CY - Berlin

ER -