  


On semidefinite programming relaxations of maximum ksection
Etienne De Klerk(e.deklerkuvt.nl) Abstract: We derive a new semidefinite programming bound for the maximum ksection problem. For k=2 (i.e. for maximum bisection), the new bound is least as strong as the wellknown bound by Frieze and Jerrum [A. Frieze and M. Jerrum. Improved Approximation Algorithms for MAX kCUT and MAX BISECTION. Algorithmica, 18(1): 6781, 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 InteriorPoint 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 (Semidefinite 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 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  