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 (Topic...
| Main Authors: | , , , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
2012
|
| _version_ | 1797050269891035136 |
|---|---|
| author | De Klerk, E Pasechnik, D Sotirov, R Dobre, C |
| author_facet | De Klerk, E Pasechnik, D Sotirov, R Dobre, C |
| author_sort | De Klerk, E |
| collection | OXFORD |
| 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. © 2012 Springer-Verlag Berlin Heidelberg and Mathematical Optimization Society. |
| first_indexed | 2024-03-06T18:02:41Z |
| format | Journal article |
| id | oxford-uuid:005b11cb-6084-40f2-8280-b509a50e840d |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-06T18:02:41Z |
| publishDate | 2012 |
| record_format | dspace |
| spelling | oxford-uuid:005b11cb-6084-40f2-8280-b509a50e840d2022-03-26T08:29:04ZOn semidefinite programming relaxations of maximum k-sectionJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:005b11cb-6084-40f2-8280-b509a50e840dEnglishSymplectic Elements at Oxford2012De Klerk, EPasechnik, DSotirov, RDobre, CWe 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. © 2012 Springer-Verlag Berlin Heidelberg and Mathematical Optimization Society. |
| spellingShingle | De Klerk, E Pasechnik, D Sotirov, R Dobre, C On semidefinite programming relaxations of maximum k-section |
| title | 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_short | On semidefinite programming relaxations of maximum k-section |
| title_sort | on semidefinite programming relaxations of maximum k section |
| work_keys_str_mv | AT deklerke onsemidefiniteprogrammingrelaxationsofmaximumksection AT pasechnikd onsemidefiniteprogrammingrelaxationsofmaximumksection AT sotirovr onsemidefiniteprogrammingrelaxationsofmaximumksection AT dobrec onsemidefiniteprogrammingrelaxationsofmaximumksection |