### Abstract

*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*≥ 3the 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.

Original language | English |
---|---|

Pages (from-to) | 253-278 |

Journal | Mathematical Programming |

Volume | 136 |

Issue number | 2 |

Publication status | Published - 2012 |

### Fingerprint

### Cite this

*Mathematical Programming*,

*136*(2), 253-278.

}

*Mathematical Programming*, vol. 136, no. 2, pp. 253-278.

**On semidefinite programming relaxations of maximum k-section.** / de Klerk, E.; Pasechnik, D.V.; Sotirov, R.; Dobre, C.

Research output: Contribution to journal › Article › Scientific › peer-review

TY - JOUR

T1 - On semidefinite programming relaxations of maximum k-section

AU - de Klerk, E.

AU - Pasechnik, D.V.

AU - Sotirov, R.

AU - Dobre, C.

PY - 2012

Y1 - 2012

N2 - 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 ≥ 3the 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.

AB - 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 ≥ 3the 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.

M3 - Article

VL - 136

SP - 253

EP - 278

JO - Mathematical Programming

JF - Mathematical Programming

SN - 0025-5610

IS - 2

ER -