An approximation algorithm for max k-uncut with capacity constraints

DOI10.1080/02331934.2011.592527zbMATH Open1236.05194OpenAlexW2169649212MaRDI QIDQ3225074FDOQ3225074

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

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

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)

Cites Work

• Approximation algorithms for maximization problems arising in graph partitioning
• The Complexity of Multiterminal Cuts
• Improved approximation algorithms for MAX \(k\)-cut and MAX BISECTION
• P-Complete Approximation Problems
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Finding k Cuts within Twice the Optimal
• Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming
• An approximation algorithm for max \(k\)-uncut with capacity constraints
• Title not available (Why is that?)
• 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

Cited In (9)

• 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
• An approximation algorithm for max \(k\)-uncut with capacity constraints

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)