On semidefinite programming relaxations of maximum k-section

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

Research output: Contribution to journalArticleScientificpeer-review

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 ≥ 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
Volume136
Issue number2
Publication statusPublished - 2012

    Fingerprint

Cite this