An approximation algorithm for maxk-uncut with capacity constraints

DOI10.1080/02331934.2011.592527zbMath1236.05194OpenAlexW2169649212MaRDI QIDQ3225074

Ramesh Krishnamurti, Salimur Choudhury, Daya Ram Gaur

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)

Related Items (6)

Approximation and hardness results for the max \(k\)-uncut problem ⋮ An approximation algorithm for the balanced Max-3-Uncut problem using complex semidefinite programming rounding ⋮ An approximation algorithm for maxk-uncut with capacity constraints ⋮ Approximation and Hardness Results for the Max k-Uncut Problem ⋮ New algorithms for a simple measure of network partitioning ⋮ New algorithms for a simple measure of network partitioning

Cites Work

• Unnamed Item
• Improved approximation algorithms for MAX \(k\)-cut and MAX BISECTION
• 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
• An approximation algorithm for maxk-uncut with capacity constraints
• P-Complete Approximation Problems
• The Complexity of Multiterminal Cuts
• Finding k Cuts within Twice the Optimal
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming

This page was built for publication: An approximation algorithm for maxk-uncut with capacity constraints