On semidefinite programming relaxations of maximum k -section
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...
Saved in:
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
2013
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/10356/97683 http://hdl.handle.net/10220/11138 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Institution: | Nanyang Technological University |
| Language: | English |
| id |
sg-ntu-dr.10356-97683 |
|---|---|
| record_format |
dspace |
| spelling |
sg-ntu-dr.10356-976832020-03-07T12:31:32Z On semidefinite programming relaxations of maximum k -section Klerk, Etienne de. Pasechnik, Dmitrii V. Sotirov, Renata. Dobre, Cristian. School of Physical and Mathematical Sciences DRNTU::Science::Mathematics 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. 2013-07-10T08:28:07Z 2019-12-06T19:45:25Z 2013-07-10T08:28:07Z 2019-12-06T19:45:25Z 2012 2012 Journal Article https://hdl.handle.net/10356/97683 http://hdl.handle.net/10220/11138 10.1007/s10107-012-0603-2 en Mathematical programming © 2012 Springer-Verlag Berlin Heidelberg and Mathematical Optimization Society. |
| institution |
Nanyang Technological University |
| building |
NTU Library |
| country |
Singapore |
| collection |
DR-NTU |
| language |
English |
| topic |
DRNTU::Science::Mathematics |
| spellingShingle |
DRNTU::Science::Mathematics Klerk, Etienne de. Pasechnik, Dmitrii V. Sotirov, Renata. Dobre, Cristian. On semidefinite programming relaxations of maximum k -section |
| description |
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. |
| author2 |
School of Physical and Mathematical Sciences |
| author_facet |
School of Physical and Mathematical Sciences Klerk, Etienne de. Pasechnik, Dmitrii V. Sotirov, Renata. Dobre, Cristian. |
| format |
Article |
| author |
Klerk, Etienne de. Pasechnik, Dmitrii V. Sotirov, Renata. Dobre, Cristian. |
| author_sort |
Klerk, Etienne de. |
| title |
On semidefinite programming relaxations of maximum k -section |
| title_short |
On semidefinite programming relaxations of maximum k -section |
| title_full |
On semidefinite programming relaxations of maximum k -section |
| title_fullStr |
On semidefinite programming relaxations of maximum k -section |
| title_full_unstemmed |
On semidefinite programming relaxations of maximum k -section |
| title_sort |
on semidefinite programming relaxations of maximum k -section |
| publishDate |
2013 |
| url |
https://hdl.handle.net/10356/97683 http://hdl.handle.net/10220/11138 |
| _version_ |
1681048676921769984 |