On duality and fractionality of multicommodity flows in directed networks

From MaRDI portal
Publication:665994

DOI10.1016/J.DISOPT.2011.03.001zbMATH Open1261.90044arXiv1006.5520OpenAlexW2043489833MaRDI QIDQ665994FDOQ665994


Authors: Hiroshi Hirai, Shungo Koichi Edit this on Wikidata


Publication date: 7 March 2012

Published in: Discrete Optimization (Search for Journal in Brave)

Abstract: In this paper we address a topological approach to multiflow (multicommodity flow) problems in directed networks. Given a terminal weight mu, we define a metrized polyhedral complex, called the directed tight span Tmu, and prove that the dual of mu-weighted maximum multiflow problem reduces to a facility location problem on Tmu. Also, in case where the network is Eulerian, it further reduces to a facility location problem on the tropical polytope spanned by mu. By utilizing this duality, we establish the classifications of terminal weights admitting combinatorial min-max relation (i) for every network and (ii) for every Eulerian network. Our result includes Lomonosov-Frank theorem for directed free multiflows and Ibaraki-Karzanov-Nagamochi's directed multiflow locking theorem as special cases.


Full work available at URL: https://arxiv.org/abs/1006.5520




Recommendations




Cites Work


Cited In (8)





This page was built for publication: On duality and fractionality of multicommodity flows in directed networks

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