Exploiting sparsity for the min k-partition problem
From MaRDI portal
Publication:2175445
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 prohibitive number of valid inequalities and integer variables. In this work, we introduce two compact integer linear and semidefinite reformulations that exploit the sparsity of the underlying graph and develop fundamental results leveraging the power of chordal decomposition. Numerical experiments show that the new formulations improve upon state-of-the-art.
Recommendations
- Improved compact formulations for a wide class of graph partitioning problems in sparse graphs
- Projection results for the \(k\)-partition problem
- A branch-and-cut algorithm based on semidefinite programming for the minimum \(k\)-partition problem
- An extended edge-representative formulation for the \(K\)-partitioning problem
- Polyhedral combinatorics of the \(K\)-partitioning problem with representative variables
Cites work
- A branch-and-cut algorithm based on semidefinite programming for the minimum \(k\)-partition problem
- A connection between positive semidefinite and Euclidean distance matrix completion problems
- A Lagrange decomposition based branch and bound algorithm for the optimal mapping of cloud virtual machines
- Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
- Clique-Web Facets for Multicut Polytopes
- Computational study of valid inequalities for the maximum \(k\)-cut problem
- Computing the Minimum Fill-In is NP-Complete
- Convergent SDP‐Relaxations in Polynomial Optimization with Sparsity
- Convex and concave envelopes: revisited and new perspectives
- Exploiting sparsity in linear and nonlinear matrix inequalities via positive semidefinite matrix completion
- Exploiting sparsity in semidefinite programming via matrix completion. I: General framework
- Exploiting sparsity in semidefinite programming via matrix completion. II: Implementation and numerical results
- Facets of the \(k\)-partition polytope
- scientific article; zbMATH DE number 3859178 (Why is no real title available?)
- scientific article; zbMATH DE number 17641 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 554762 (Why is no real title available?)
- scientific article; zbMATH DE number 2086928 (Why is no real title available?)
- scientific article; zbMATH DE number 3322854 (Why is no real title available?)
- Improved approximation algorithms for MAX k-cut and MAX BISECTION
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Incidence matrices and interval graphs
- Linear time algorithms for NP-hard problems restricted to partial k- trees
- LP formulations for polynomial optimization problems
- On the cut polytope
- Orbitopal fixing
- Positive definite completions of partial Hermitian matrices
- Projection results for the \(k\)-partition problem
- Scheduling to Minimize Interaction Cost
- Solving k-way graph partitioning problems to optimality: the impact of semidefinite relaxations and the bundle method
- Sums of Squares and Semidefinite Program Relaxations for Polynomial Optimization Problems with Structured Sparsity
- The partition problem
- Tree-width and the Sherali-Adams operator
- Treewidth computations. I: Upper bounds
- Treewidth: computational experiments
Cited in
(8)- Projection results for the \(k\)-partition problem
- A branch-and-bound algorithm for solving max-\(k\)-cut problem
- Improving the linear relaxation of maximum \(k\)-cut with semidefinite-based constraints
- Sparsity of integer formulations for binary programs
- Computational study of a branching algorithm for the maximum \(k\)-cut problem
- An extended edge-representative formulation for the \(K\)-partitioning problem
- Solving graph partitioning on sparse graphs: cuts, projections, and extended formulations
- A folding preprocess for the max k-cut problem
This page was built for publication: Exploiting sparsity for the min \(k\)-partition problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2175445)
