On semidefinite programming relaxations of maximum k-section

Etienne De Klerk; Dmitrii Pasechnik; Renata Sotirov; Cristian Dobre

doi:10.1007/s10107-012-0603-2

On semidefinite programming relaxations of maximum k-section

Etienne De Klerk^*, Dmitrii Pasechnik, Renata Sotirov, Cristian Dobre

^*Corresponding author for this work

Computer Science

Research output: Contribution to journal › Article › peer-review

11 Scopus citations

Abstract

We derive a new semidefinite programming bound for the maximum k-section problem. For k=2 (i.e. for maximum bisection), the new bound is at least as strong as a well-known bound by Poljak and Rendl (SIAM J Optim 5(3):467-487, 1995). For k≥3 the new bound dominates a bound of Karisch and Rendl (Topics in semidefinite and interior-point methods, 1998). The new bound is derived from a recent semidefinite programming bound by De Klerk and Sotirov for the more general quadratic assignment problem, but only requires the solution of a much smaller semidefinite program.

Original language	English (US)
Pages (from-to)	253-278
Number of pages	26
Journal	Mathematical Programming
Volume	136
Issue number	2
DOIs	https://doi.org/10.1007/s10107-012-0603-2
State	Published - Dec 2012

Keywords

Coherent configurations
Maximum bisection
Maximum section
Semidefinite programming
Strongly regular graph

ASJC Scopus subject areas

Software
General Mathematics

Access to Document

10.1007/s10107-012-0603-2

Cite this

@article{fa5deae5a8a546d58bc37e94c55c9bdc,

title = "On semidefinite programming relaxations of maximum k-section",

abstract = "We derive a new semidefinite programming bound for the maximum k-section problem. For k=2 (i.e. for maximum bisection), the new bound is at least as strong as a well-known bound by Poljak and Rendl (SIAM J Optim 5(3):467-487, 1995). For k≥3 the new bound dominates a bound of Karisch and Rendl (Topics in semidefinite and interior-point methods, 1998). The new bound is derived from a recent semidefinite programming bound by De Klerk and Sotirov for the more general quadratic assignment problem, but only requires the solution of a much smaller semidefinite program.",

keywords = "Coherent configurations, Maximum bisection, Maximum section, Semidefinite programming, Strongly regular graph",

author = "{De Klerk}, Etienne and Dmitrii Pasechnik and Renata Sotirov and Cristian Dobre",

year = "2012",

month = dec,

doi = "10.1007/s10107-012-0603-2",

language = "English (US)",

volume = "136",

pages = "253--278",

journal = "Mathematical Programming",

issn = "0025-5610",

publisher = "Springer-Verlag GmbH and Co. KG",

number = "2",

}

TY - JOUR

T1 - On semidefinite programming relaxations of maximum k-section

AU - De Klerk, Etienne

AU - Pasechnik, Dmitrii

AU - Sotirov, Renata

AU - Dobre, Cristian

PY - 2012/12

Y1 - 2012/12

N2 - We derive a new semidefinite programming bound for the maximum k-section problem. For k=2 (i.e. for maximum bisection), the new bound is at least as strong as a well-known bound by Poljak and Rendl (SIAM J Optim 5(3):467-487, 1995). For k≥3 the new bound dominates a bound of Karisch and Rendl (Topics in semidefinite and interior-point methods, 1998). The new bound is derived from a recent semidefinite programming bound by De Klerk and Sotirov for the more general quadratic assignment problem, but only requires the solution of a much smaller semidefinite program.

AB - We derive a new semidefinite programming bound for the maximum k-section problem. For k=2 (i.e. for maximum bisection), the new bound is at least as strong as a well-known bound by Poljak and Rendl (SIAM J Optim 5(3):467-487, 1995). For k≥3 the new bound dominates a bound of Karisch and Rendl (Topics in semidefinite and interior-point methods, 1998). The new bound is derived from a recent semidefinite programming bound by De Klerk and Sotirov for the more general quadratic assignment problem, but only requires the solution of a much smaller semidefinite program.

KW - Coherent configurations

KW - Maximum bisection

KW - Maximum section

KW - Semidefinite programming

KW - Strongly regular graph

UR - http://www.scopus.com/inward/record.url?scp=84870376057&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84870376057&partnerID=8YFLogxK

U2 - 10.1007/s10107-012-0603-2

DO - 10.1007/s10107-012-0603-2

M3 - Article

AN - SCOPUS:84870376057

SN - 0025-5610

VL - 136

SP - 253

EP - 278

JO - Mathematical Programming

JF - Mathematical Programming

IS - 2

ER -

On semidefinite programming relaxations of maximum k-section

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this