On semidefinite programming relaxations of maximum k-section

E. de Klerk, D.V. Pasechnik, R. Sotirov, C. Dobre

Research output: Contribution to journalArticleScientificpeer-review

11 Citations (Scopus)


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 ≥ 3the 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 languageEnglish
Pages (from-to)253-278
JournalMathematical Programming
Issue number2
Publication statusPublished - 2012


Dive into the research topics of 'On semidefinite programming relaxations of maximum k-section'. Together they form a unique fingerprint.

Cite this