An approximation algorithm for max k-uncut with capacity constraints

DOI10.1080/02331934.2011.592527MaRDI QIDQ3225074zbMATH OpenOpenAlexFDO

Authors Salimur Choudhury, Daya Ram Gaur, Ramesh Krishnamurti

Publication date 15 March 2012

Published in Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1080/02331934.2011.592527

zbMATH Keywords

local searchcapacity constraintsMax \(k\)-uncutunbalanced partition

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Graph algorithms (graph-theoretic aspects) (05C85) Signed and weighted graphs (05C22)

Recommendations

• Approximation and hardness results for the max \(k\)-uncut problem
• The capacitated max \(k\)-cut problem
• scientific article; zbMATH DE number 1670644
• Approximation algorithms for maximum cut with limited unbalance
• On approximation of max \(\frac{n}{2}\)-uncut problem

Cites work

• scientific article; zbMATH DE number 1304324 (Why is no real title available?)
• A 0. 5-approximation algorithm for MAX DICUT with given sizes of parts
• An approximation algorithm for max \(k\)-uncut with capacity constraints
• Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming
• Approximation algorithms for maximization problems arising in graph partitioning
• Finding k Cuts within Twice the Optimal
• 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 -function
• P-Complete Approximation Problems
• The Complexity of Multiterminal Cuts

Cited in

(9)

• An approximation algorithm for max \(k\)-uncut with capacity constraints
• Sum-max graph partitioning problem
• Approximation and hardness results for the max \(k\)-uncut problem
• Approximation and hardness results for the max \(k\)-uncut problem
• Nonuniform graph partitioning with unrelated weights
• An approximation algorithm for the balanced Max-3-Uncut problem using complex semidefinite programming rounding
• New algorithms for a simple measure of network partitioning
• New algorithms for a simple measure of network partitioning
• The capacitated max \(k\)-cut problem

This page was built for publication: An approximation algorithm for max \(k\)-uncut with capacity constraints

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