Improved approximation for directed cut problems
From MaRDI portal
Publication:3549668
DOI10.1145/1250790.1250888zbMath1232.68176OpenAlexW2009924457MaRDI QIDQ3549668
Amit Agarwal, Noga Alon, Moses Charikar
Publication date: 5 January 2009
Published in: Proceedings of the thirty-ninth annual ACM symposium on Theory of computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1250790.1250888
LP relaxationdirected multicutapproximation algirthmsdirected sparsest cutrandomized rounding algorithm
Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Directed graphs (digraphs), tournaments (05C20)
Related Items (12)
Designing FPT Algorithms for Cut Problems Using Randomized Contractions ⋮ Vertex downgrading to minimize connectivity ⋮ Cut-sufficient directed 2-commodity multiflow topologies ⋮ Approximation and hardness results for label cut and related problems ⋮ On the advantage of overlapping clusters for minimizing conductance ⋮ Evader interdiction: algorithms, complexity and collateral damage ⋮ Register loading via linear programming ⋮ Multi-Budgeted Directed Cuts ⋮ The checkpoint problem ⋮ Quasimetric embeddings and their applications ⋮ Multicommodity flows and cuts in polymatroidal networks ⋮ Multi-budgeted directed cuts
This page was built for publication: Improved approximation for directed cut problems
