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
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 , we define a metrized polyhedral complex, called the directed tight span , and prove that the dual of -weighted maximum multiflow problem reduces to a facility location problem on . Also, in case where the network is Eulerian, it further reduces to a facility location problem on the tropical polytope spanned by . 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
- Tight spans of distances and the dual fractionality of undirected multiflow problems
- Minimum cost multiflows in undirected networks
- The maximum multiflow problems with bounded fractionality
- Folder complexes and multiflow combinatorial dualities
- The maximum multiflow problems with bounded fractionality
Cites Work
- Title not available (Why is that?)
- Trees, tight extensions of metric spaces, and the cohomological dimension of certain groups: A note on combinatorial properties of metric spaces
- Tropical convexity
- Six theorems about injective metric spaces
- Tight spans of distances and the dual fractionality of undirected multiflow problems
- Polyhedra related to undirected multicommodity flows
- Metrics with finite sets of primitive extensions
- Minimum 0-extensions of graph metrics
- On tight spans for directed distances
- Characterization of the distance between subtrees of a tree by the associated tight span
- Folder complexes and multiflow combinatorial dualities
- A fast algorithm for finding a maximum free multiflow in an inner Eulerian network and some generalizatons
- Title not available (Why is that?)
Cited In (8)
- A note on multiflow locking theorem
- Euler digraphs
- Tight spans of distances and the dual fractionality of undirected multiflow problems
- \(T_X\)-approaches to multiflows and metrics
- Folder complexes and multiflow combinatorial dualities
- On tight spans for directed distances
- Half-integrality of node-capacitated multiflows and tree-shaped facility locations on trees
- On fractional multicommodity flows and distance functions
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)