Projection results for the \(k\)-partition problem
From MaRDI portal
Publication:1751250
DOI10.1016/j.disopt.2017.08.001zbMath1387.90213OpenAlexW2751855500MaRDI QIDQ1751250
Jamie Fairbrother, Adam N. Letchford
Publication date: 24 May 2018
Published in: Discrete Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.disopt.2017.08.001
Semidefinite programming (90C22) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
Computational study of valid inequalities for the maximum \(k\)-cut problem, Exploiting sparsity for the min \(k\)-partition problem, Computational study of a branching algorithm for the maximum \(k\)-cut problem, On Integrality in Semidefinite Programming for Discrete Optimization, A two-level graph partitioning problem arising in mobile wireless communications, Global optimization of multilevel electricity market models including network design and graph partitioning, Improving the linear relaxation of maximum \(k\)-cut with semidefinite-based constraints
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Orbitopal fixing
- A branch-and-cut algorithm based on semidefinite programming for the minimum \(k\)-partition problem
- Binary positive semidefinite matrices and associated integer polytopes
- Improved approximation algorithms for MAX \(k\)-cut and MAX BISECTION
- Facets of the clique partitioning polytope
- New bounds for the \(\max\)-\(k\)-cut and chromatic number of a graph
- A cutting plane algorithm for a clustering problem
- Geometric algorithms and combinatorial optimization
- Some simplified NP-complete graph problems
- Lifting theorems and facet characterization for a class of clique partitioning inequalities
- Set packing relaxations of some integer programs
- \(\{ 0,\frac12\}\)-Chvátal-Gomory cuts
- On approximate graph colouring and MAX-\(k\)-CUT algorithms based on the \(\vartheta\)-function
- Facets of the \(k\)-partition polytope
- Gap inequalities for the cut polytope
- The partition problem
- An Efficient Semidefinite Programming Relaxation for the Graph Partition Problem
- Testing the Odd Bicycle Wheel Inequalities for the Bipartite Subgraph Polytope
- Clique-Web Facets for Multicut Polytopes
- The Graph Partitioning Polytope on Series-Parallel and 4-Wheel Free Graphs
- The clique partitioning problem: Facets and patching facets
- On the cut polytope
- Transitive Packing: A Unifying Concept in Combinatorial Optimization
- Scheduling to Minimize Interaction Cost
- A Note on Clique-Web Facets for Multicut Polytopes
- Semidefinite relaxations for partitioning, assignment and ordering problems
- On disjunctive cuts for combinatorial optimization
