On semidefinite programming relaxations of maximum k-section

• 成果类型: Article
• 署名作者: de Klerk, Etienne; Pasechnik, Dmitrii; Sotirov, Renata; Dobre, Cristian
• 署名单位: Tilburg University; Nanyang Technological University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-012-0603-2
• 发表日期: 2012
• 页码: 253-278
• 关键词: improved approximation algorithms; quadratic assignment problem; graph-bisection problems; max-bisection; symmetry; bounds; cut

摘要

We derive a new semidefinite programming bound for the maximum -section problem. For (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 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.