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
|