TY  - JOUR
U1  - Wissenschaftlicher Artikel
A1  - Wang, Guanglei
A1  - Hijazi, Hassan
T1  - Exploiting sparsity for the min k-partition problem
JF  - Mathematical Programming Computation
N2  - The minimum k-partition problem is a challenging combinatorial problem with a diverse set of applications ranging from telecommunications to sports scheduling. It generalizes the max-cut problem and has been extensively studied since the late sixties. Strong integer formulations proposed in the literature suffer from a large number of constraints and variables. In this work, we introduce two more compact integer linear and semidefinite reformulations that exploit the sparsity of the underlying graph and develop theoretical results leveraging the power of chordal decomposition. Numerical experiments show that the new formulations improve upon state-of-the-art.
AB  - The minimum k-partition problem is a challenging combinatorial problem with a diverse set of applications ranging from telecommunications to sports scheduling. It generalizes the max-cut problem and has been extensively studied since the late sixties. Strong integer formulations proposed in the literature suffer from a large number of constraints and variables. In this work, we introduce two more compact integer linear and semidefinite reformulations that exploit the sparsity of the underlying graph and develop theoretical results leveraging the power of chordal decomposition. Numerical experiments show that the new formulations improve upon state-of-the-art.
KW  - Software
KW  - Theoretical Computer Science
Y1  - 2019
SN  - 1867-2949
SS  - 1867-2949
U6  - https://doi.org/10.1007/s12532-019-00165-3
DO  - https://doi.org/10.1007/s12532-019-00165-3
VL  - 12
IS  - 1
SP  - 109
EP  - 130
S1  - 22
PB  - Springer Science and Business Media LLC
ER  -