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 ≥ 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.
|Publication status||Published - 2012|
de Klerk, E., Pasechnik, D. V., Sotirov, R., & Dobre, C. (2012). On semidefinite programming relaxations of maximum k-section. Mathematical Programming , 136(2), 253-278. http://link.springer.com/article/10.1007%2Fs10107-012-0603-2?LI=true#