On semidefinite programming relaxations of maximum k-section

Journal article

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. © 2012 Springer-Verlag Berlin Heidelberg and Mathematical Optimization Society.

Authors: De Klerk, E; Pasechnik, D; Sotirov, R; Dobre, C

• Journal: Mathematical Programming
• Volume: 136
• Issue: 2
• Pages: 253-278
• Publication date: 2012-12-01
• DOI: 10.1007/s10107-012-0603-2
• EISSN: 1436-4646
• ISSN: 0025-5610
• Language: English
• Keywords: Maximum section; Strongly regular graph; Maximum bisection; Semidefinite programming; Coherent configurations