Exploiting sparsity for the min \(k\)-partition problem
From MaRDI portal
Publication:2175445
DOI10.1007/s12532-019-00165-3zbMath1437.90143arXiv1709.00485OpenAlexW2963760933WikidataQ127597281 ScholiaQ127597281MaRDI QIDQ2175445
Publication date: 29 April 2020
Published in: Mathematical Programming Computation (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1709.00485
Programming involving graphs or networks (90C35) Semidefinite programming (90C22) Integer programming (90C10) Combinatorial optimization (90C27)
Related Items (3)
Computational study of a branching algorithm for the maximum \(k\)-cut problem ⋮ A branch-and-bound algorithm for solving max-\(k\)-cut problem ⋮ Improving the linear relaxation of maximum \(k\)-cut with semidefinite-based constraints
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Orbitopal fixing
- A branch-and-cut algorithm based on semidefinite programming for the minimum \(k\)-partition problem
- Improved approximation algorithms for MAX \(k\)-cut and MAX BISECTION
- Exploiting sparsity in linear and nonlinear matrix inequalities via positive semidefinite matrix completion
- Positive definite completions of partial Hermitian matrices
- Treewidth computations. I: Upper bounds
- Linear time algorithms for NP-hard problems restricted to partial k- trees
- A connection between positive semidefinite and Euclidean distance matrix completion problems
- Exploiting sparsity in semidefinite programming via matrix completion. II: Implementation and numerical results
- Computational study of valid inequalities for the maximum \(k\)-cut problem
- Convex and concave envelopes: revisited and new perspectives
- A Lagrange decomposition based branch and bound algorithm for the optimal mapping of cloud virtual machines
- Projection results for the \(k\)-partition problem
- Facets of the \(k\)-partition polytope
- The partition problem
- Tree-width and the Sherali-Adams operator
- Incidence matrices and interval graphs
- Exploiting Sparsity in Semidefinite Programming via Matrix Completion I: General Framework
- Computing the Minimum Fill-In is NP-Complete
- Clique-Web Facets for Multicut Polytopes
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- LP Formulations for Polynomial Optimization Problems
- On the cut polytope
- 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
- Scheduling to Minimize Interaction Cost
- Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
- Convergent SDP‐Relaxations in Polynomial Optimization with Sparsity
This page was built for publication: Exploiting sparsity for the min \(k\)-partition problem
