Improved approximation for directed cut problems

DOI10.1145/1250790.1250888MaRDI QIDQ3549668zbMATH OpenOpenAlexFDO

Authors 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

zbMATH Keywords

LP relaxationdirected multicutapproximation algirthmsdirected sparsest cutrandomized rounding algorithm

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Cited in

(15)

• Cut-sufficient directed 2-commodity multiflow topologies
• Designing FPT algorithms for cut problems using randomized contractions
• On the parameterized complexity of symmetric directed multicut
• Multi-budgeted directed cuts
• Multi-budgeted directed cuts
• Vertex downgrading to minimize connectivity
• Evader interdiction: algorithms, complexity and collateral damage
• On the advantage of overlapping clusters for minimizing conductance
• Parameterized inapproximability for Steiner orientation by gap amplification
• Cut-sufficient directed 2-commodity multiflow topologies
• Approximate cut \& packing ratios for multi-commodity arborescences
• Register loading via linear programming
• The checkpoint problem
• Quasimetric embeddings and their applications
• Approximation and hardness results for label cut and related problems

This page was built for publication: Improved approximation for directed cut problems

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