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 least as strong as the well-known bound by Frieze and Jerrum [A. Frieze and M. Jerrum. Improved Approximation Algorithms for MAX k-CUT and MAX BISECTION. Algorithmica, 18(1): 67-81, 1997]. For k > 2 the new bound dominates a bound of Karish and Rendl [S.E. Karish, F. Rendl. Semidefinite Programming and Graph Equipartition. In: Topics in Semidefinite and Interior-Point Methods, P.M. Pardalos and H. Wolkowicz, Eds., 1998.] The new bound is derived from a recent semidefinite programming bound by De Klerk and Sotirov for the more general quadratic assignment problem (QAP), but only requires the solution of a much smaller semidefinite program.
Citation
Preprint, Tilburg University, The Netherlands, June, 2010