On semidefinite programming relaxations of maximum k -section

• المؤلفون الرئيسيون: Klerk, Etienne de., Pasechnik, Dmitrii V., Sotirov, Renata., Dobre, Cristian.
• مؤلفون آخرون: School of Physical and Mathematical Sciences
• التنسيق: مقال
• اللغة: English
• منشور في: 2013
• الموضوعات: DRNTU::Science::Mathematics
• الوصول للمادة أونلاين: https://hdl.handle.net/10356/97683; http://hdl.handle.net/10220/11138

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...