On duality and fractionality of multicommodity flows in directed networks

DOI10.1016/J.DISOPT.2011.03.001MaRDI QIDQ665994zbMATH OpenOpenAlexFDO

Authors Hiroshi Hirai, Shungo Koichi

Publication date 7 March 2012

Published in Discrete Optimization (Search for Journal in Brave)

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

zbMATH Keywords

metricsmulticommodity flowsmin-max theoremsfacility locations

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Flows in graphs (05C21)

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 $T_{mu}$, and prove that the dual of $mu$-weighted maximum multiflow problem reduces to a facility location problem on $T_{mu}$. 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.

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

• scientific article; zbMATH DE number 4089320 (Why is no real title available?)
• scientific article; zbMATH DE number 4103110 (Why is no real title available?)
• A fast algorithm for finding a maximum free multiflow in an inner Eulerian network and some generalizatons
• Characterization of the distance between subtrees of a tree by the associated tight span
• Folder complexes and multiflow combinatorial dualities
• Metrics with finite sets of primitive extensions
• Minimum 0-extensions of graph metrics
• On tight spans for directed distances
• Polyhedra related to undirected multicommodity flows
• Six theorems about injective metric spaces
• Tight spans of distances and the dual fractionality of undirected multiflow problems
• Trees, tight extensions of metric spaces, and the cohomological dimension of certain groups: A note on combinatorial properties of metric spaces
• Tropical convexity

Cited in

(9)

• On tight spans for directed distances
• Folder complexes and multiflow combinatorial dualities
• A note on multiflow locking theorem
• Cut-sufficient directed 2-commodity multiflow topologies
• \(T_X\)-approaches to multiflows and metrics
• Tight spans of distances and the dual fractionality of undirected multiflow problems
• Half-integrality of node-capacitated multiflows and tree-shaped facility locations on trees
• On fractional multicommodity flows and distance functions
• Euler digraphs

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)