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/ISSN › Chapter (peer-reviewed) › peer-review
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). doi: 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 -