On semidefinite programming relaxations of maximum k-section

E. de Klerk, D.V. Pasechnik, R. Sotirov, C. Dobre

Research output: Contribution to journalArticleScientificpeer-review

Abstract

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 ≥ 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 languageEnglish
Pages (from-to)253-278
JournalMathematical Programming
Volume136
Issue number2
Publication statusPublished - 2012

Fingerprint

Semidefinite Programming Relaxation
Semidefinite Programming
Semidefinite Program
Quadratic Assignment Problem
Bisection
Interior Point Method

Cite this

@article{55c9ecb99eb44444a52822df67cfe976,
title = "On semidefinite programming relaxations of maximum k-section",
abstract = "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.",
author = "{de Klerk}, E. and D.V. Pasechnik and R. Sotirov and C. Dobre",
year = "2012",
language = "English",
volume = "136",
pages = "253--278",
journal = "Mathematical Programming",
issn = "0025-5610",
publisher = "Springer",
number = "2",

}

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

In: Mathematical Programming , Vol. 136, No. 2, 2012, p. 253-278.

Research output: Contribution to journalArticleScientificpeer-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 -