A lower bound on the integrality gap for minimum multicut in directed networks

DOI10.1007/S00493-004-0031-XMaRDI QIDQ705752zbMATH OpenOpenAlexFDO

Authors Alex Samorodnitsky, Leonid Zosin, Michael Saks

Publication date 14 February 2005

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00493-004-0031-x

zbMATH Keywords

directed networks

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Deterministic network models in operations research (90B10) Programming involving graphs or networks (90C35)

Recommendations

• Polynomial flow-cut gaps and hardness of directed cut problems
• Hardness of cut problems in directed graphs
• Approximating directed multicuts
• scientific article; zbMATH DE number 2079369
• A 2-approximation algorithm for the directed multiway cut problem

Cited in

(8)

• An O( n)-approximation algorithm for directed sparsest cut
• Approximating minimum feedback sets and multicuts in directed graphs
• Eliminating cycles in the discrete torus
• ECONOMICAL TORIC SPINES VIA CHEEGER'S INEQUALITY
• Polynomial flow-cut gaps and hardness of directed cut problems
• Approximate cut \& packing ratios for multi-commodity arborescences
• On the Max-flow min-cut ratio for directed multicommodity flows
• The all-or-nothing flow problem in directed graphs with symmetric demand pairs

This page was built for publication: A lower bound on the integrality gap for minimum multicut in directed networks

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