Please use this identifier to cite or link to this item:
|Title:||On semidefinite programming relaxations of maximum k -section||Authors:||Klerk, Etienne de.
Pasechnik, Dmitrii V.
|Keywords:||DRNTU::Science::Mathematics||Issue Date:||2012||Series/Report no.:||Mathematical programming||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 k≥3 the 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.||URI:||https://hdl.handle.net/10356/97683
|DOI:||10.1007/s10107-012-0603-2||Rights:||© 2012 Springer-Verlag Berlin Heidelberg and Mathematical Optimization Society.||Fulltext Permission:||none||Fulltext Availability:||No Fulltext|
|Appears in Collections:||SPMS Journal Articles|
Updated on Jan 19, 2023
Web of ScienceTM
Updated on Jan 31, 2023
Page view(s) 50410
Updated on Feb 5, 2023
Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.