Projection results for the \(k\)-partition problem

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

zbMATH Keywords

semidefinite programminggraph partitioningbranch-and-cutpolyhedral combinatorics

Mathematics Subject Classification ID

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

• Gurobi
• igraph

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