The capacitated max \(k\)-cut problem

DOI10.1007/s10107-007-0139-zzbMath1145.90058OpenAlexW2004699374MaRDI QIDQ930343

Ramesh Krishnamurti, Daya Ram Gaur, Rajeev Kohli

Publication date: 30 June 2008

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10107-007-0139-z

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Related Items (5)

\(p\)-Laplace operators for oriented hypergraphs ⋮ Computational study of valid inequalities for the maximum \(k\)-cut problem ⋮ On Integrality in Semidefinite Programming for Discrete Optimization ⋮ A VNS metaheuristic with stochastic steps for Max 3-cut and Max 3-section ⋮ New Formulations for the Conflict Resolution Problem in the Scheduling of Television Commercials

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Improved approximation algorithms for MAX \(k\)-cut and MAX BISECTION
• How easy is local search?
• Stowage planning for container ships to reduce the number of shifts
• Container ship stowage problem complexity and connection to the coloring of circle graphs
• Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming
• On approximate graph colouring and MAX-\(k\)-CUT algorithms based on the \(\vartheta\)-function
• A 0.5-Approximation Algorithm for MAX DICUT with Given Sizes of Parts
• Approximation Algorithms for Maximization Problems Arising in Graph Partitioning
• Scheduling Commercials on Broadcast Television
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Approximate Local Search in Combinatorial Optimization
• A .699-approximation algorithm for Max-Bisection.

This page was built for publication: The capacitated max \(k\)-cut problem