Please use this identifier to cite or link to this item: https://hdl.handle.net/10356/97683
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.
URI: https://hdl.handle.net/10356/97683
http://hdl.handle.net/10220/11138
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

SCOPUSTM   
Citations 20

10
Updated on Jan 19, 2023

Web of ScienceTM
Citations 20

10
Updated on Jan 31, 2023

Page view(s) 50

410
Updated on Feb 5, 2023

Google ScholarTM

Check

Altmetric


Plumx

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