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

DOI10.1007/s00493-004-0031-xzbMath1058.05033OpenAlexW1986291656MaRDI QIDQ705752

Leonid Zosin, Alex Samorodnitsky, Michael E. 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

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

Related Items (6)

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

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