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

DOI10.1007/S00493-004-0031-XzbMATH Open1058.05033OpenAlexW1986291656MaRDI QIDQ705752FDOQ705752

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

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

zbMATH Keywords

directed networks

Mathematics Subject Classification ID

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

Cited In (7)

• On the Max-flow min-cut ratio for directed multicommodity flows
• Multicommodity flows and cuts in polymatroidal networks
• The all-or-nothing flow problem in directed graphs with symmetric demand pairs
• Approximating minimum feedback sets and multicuts in directed graphs
• An \(O(\sqrt n)\)-approximation algorithm for directed sparsest cut
• Eliminating cycles in the discrete torus
• ECONOMICAL TORIC SPINES VIA CHEEGER'S INEQUALITY

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)