DOE OSTI · 1688737
Exploiting sparsity for the min k -partition problem
Abstract
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. Here, 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.
Explore related subjects
Keep this discovery
Explore connections, maps & timelines
Wang, Guanglei, Hijazi, Hassan Lionel. 2019-07-02. Exploiting sparsity for the min k -partition problem. https://doi.org/10.1007/s12532-019-00165-3. https://searchnasa.com/record/osti%3A1688737/exploiting-sparsity-for-the-min-k-partition-problem
Citations retain the original authors and DOI and include this site’s record URL. If this discovery service contributed to your research, you can also cite Search NASA by Indiciae: BibTeX · RIS.