The capacitated max k-cut problem

DOI10.1007/S10107-007-0139-ZMaRDI QIDQ930343zbMATH OpenOpenAlexFDO

Authors Daya Ram Gaur, Ramesh Krishnamurti, 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)

Recommendations

• An approximation algorithm for max \(k\)-uncut with capacity constraints
• scientific article; zbMATH DE number 1670644
• Approximation and hardness results for the max \(k\)-uncut problem
• The node capacitated graph partitioning problem: A computational study
• The maximum cut problem

Cites work

• scientific article; zbMATH DE number 1670644 (Why is no real title available?)
• scientific article; zbMATH DE number 1304324 (Why is no real title available?)
• scientific article; zbMATH DE number 1332666 (Why is no real title available?)
• scientific article; zbMATH DE number 3793772 (Why is no real title available?)
• A .699-approximation algorithm for Max-Bisection.
• A 0. 5-approximation algorithm for MAX DICUT with given sizes of parts
• Approximate Local Search in Combinatorial Optimization
• Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming
• Approximation algorithms for maximization problems arising in graph partitioning
• Container ship stowage problem complexity and connection to the coloring of circle graphs
• How easy is local search?
• Improved approximation algorithms for MAX \(k\)-cut and MAX BISECTION
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• On approximate graph colouring and MAX-\(k\)-CUT algorithms based on the \(\vartheta\)-function
• Scheduling Commercials on Broadcast Television
• Stowage planning for container ships to reduce the number of shifts

Cited in

(8)

• Computational study of valid inequalities for the maximum \(k\)-cut problem
• A VNS metaheuristic with stochastic steps for Max 3-cut and Max 3-section
• \(p\)-Laplace operators for oriented hypergraphs
• A multiple search operator heuristic for the max-k-cut problem
• A linear time algorithm for the maximum capacity path problem
• On Integrality in Semidefinite Programming for Discrete Optimization
• An approximation algorithm for max \(k\)-uncut with capacity constraints
• New formulations for the conflict resolution problem in the scheduling of television commercials

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q930343)