Optimization Online


On semidefinite programming relaxations of maximum k-section

Etienne De Klerk(e.deklerk***at***uvt.nl)
Cristian Dobre(c.dobre***at***uvt.nl)
Dmitrii, V. Pasechnik(dima***at***ntu.edu.sg)
Renata Sotirov(r.sotirov***at***uvt.nl)

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 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.

Keywords: Maximum bisection, Maximum section, Semidefinite programming, Coherent configurations

Category 1: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Category 2: Combinatorial Optimization

Category 3: Integer Programming ((Mixed) Integer Nonlinear Programming )

Citation: Preprint, Tilburg University, The Netherlands, June, 2010

Download: [PDF]

Entry Submitted: 07/27/2010
Entry Accepted: 07/27/2010
Entry Last Modified: 07/27/2010

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society