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.
Sotirov, Renata.
Dobre, Cristian.
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.
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

Citations 20

Updated on Jan 19, 2023

Web of ScienceTM
Citations 20

Updated on Jan 31, 2023

Page view(s) 50

Updated on Feb 5, 2023

Google ScholarTM




Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.