Computational study of valid inequalities for the maximum \(k\)-cut problem

DOI10.1007/s10479-017-2448-9zbMath1392.90089OpenAlexW2404422255MaRDI QIDQ1657394

Vilmar Jefté Rodrigues de Sousa, Sébastien Le Digabel, Miguel F. Anjos

Publication date: 13 August 2018

Published in: Annals of Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10479-017-2448-9

zbMATH Keywords

semidefinite programminggraph partitioningcomputational studymaximum \(k\)-cut

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Numerical mathematical programming methods (65K05) Semidefinite programming (90C22)

Related Items

Exploiting sparsity for the min \(k\)-partition problem, A class of spectral bounds for max \(k\)-cut, Computational study of a branching algorithm for the maximum \(k\)-cut problem, A semidefinite relaxation based global algorithm for two-level graph partition problem, An exact approach for the multi-constraint graph partitioning problem, A branch-and-bound algorithm for solving max-\(k\)-cut problem, A two-level graph partitioning problem arising in mobile wireless communications, Improving the linear relaxation of maximum \(k\)-cut with semidefinite-based constraints

Uses Software

• Biq Mac
• BiqMac
• Rudy

Cites Work

• Unnamed Item
• Max \(k\)-cut and the smallest eigenvalue
• A multiple search operator heuristic for the max-k-cut problem
• 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
• Solving Max-cut to optimality by intersecting semidefinite and polyhedral relaxations
• New bounds for the \(\max\)-\(k\)-cut and chromatic number of a graph
• The capacitated max \(k\)-cut problem
• Optimization, approximation, and complexity classes
• Projection results for the \(k\)-partition problem
• Greedy randomized adaptive search procedures
• On approximate graph colouring and MAX-\(k\)-CUT algorithms based on the \(\vartheta\)-function
• Facets of the \(k\)-partition polytope
• Semidefinite programming and eigenvalue bounds for the graph partition problem
• The partition problem
• Improved semidefinite bounding procedure for solving max-cut problems to optimality
• A genetic algorithm for optimization of integrated scheduling of cranes, vehicles, and storage platforms at automated container terminals
• An Efficient Semidefinite Programming Relaxation for the Graph Partition Problem
• Testing the Odd Bicycle Wheel Inequalities for the Bipartite Subgraph Polytope
• An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design
• Clique-Web Facets for Multicut Polytopes
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Realignment in the National Football League: Did they do it right?
• Benchmarking Derivative-Free Optimization Algorithms
• Solving k-Way Graph Partitioning Problems to Optimality: The Impact of Semidefinite Relaxations and the Bundle Method
• MAX k‐CUT and approximating the chromatic number of random graphs
• Geometry of cuts and metrics
• Benchmarking optimization software with performance profiles.