Computational study of valid inequalities for the maximum \(k\)-cut problem
From MaRDI portal
Publication:1657394
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
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
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.
