Tight spans of distances and the dual fractionality of undirected multiflow problems
type: Item
instance of: scholarly article
title: Tight spans of distances and the dual fractionality of undirected multiflow problems
zbMATH Open document ID: 1190.05057
author: Hiroshi Hirai
published in: Journal of Combinatorial Theory. Series B
publication date: 2009-12-11T00:00:00Z
full work available at URL: http://hdl.handle.net/2433/126567
review text: Suppose \(G=(V,E,c)\) is an undirected graph with nonnegative capacity function \(c\) on \(E\) and suppose \(S \subseteq V\) is a set of terminals and \(\mu\) a nonnegative weight function on the set of pairs in \(S\). A path \(P\) is called an \(S\)-path if both its ends are in \(S\). A collection \(\mathcal{P}\) of \(S\)-paths together with a nonnegative flow-valued function \(\lambda\) on \(\mathcal{P}\) satisfying the capacity constraint for each \(e \in E\), \(\sum_{P\in {\mathcal{P}}:e \in P}\lambda(P) \leq c(e)\) is called a multiflow. The weighted maximum multiflow problem with respect to \(G\) and \((S, \mu)\), denoted by \(M(G;S, \mu)\) is formulated as follows: Max\(\sum_{P \in {\mathcal{P}}}\mu(s_P,t_P)\lambda(P)\) over all multiflows \((P, \lambda)\) in \(G\). The fractionality of \((S,\mu)\) is the least positive integer \(k\) such that \(M(G;S,\mu)\) has a \(1/k\)-integral optimal flow for any integer-capacitated graph \(G\) with \(S \subseteq V\). If such a \(k\) does not exist, the fractionality of \((S, \mu)\) if defined to be infinity. The problem of interest in this paper is a necessary and sufficient condition for \((S, \mu)\) to have bounded fractionality. Even the case where \(\mu\) is a \(0,1\)-function is still open. Karzanov and Lomonosov extended this to metrics \(\mu\) that are cut-decomposable. The author considers the dual \(M^*(G; S, \mu)\) of the \(M(G; S, \mu)\). A necessary and sufficient condition for \((S, \mu)\) with integral \(\mu\) to have bounded dual fractionality is obtained. This extends two fundamental results of Kazarnov: (i) the characterization of commodity graphs \(H\) for which the dual of the maximum multiflow problem with respect to \(H\) has bounded fractionality [\textit{A.V. Karzanov}, ``Undirected multiflow problems and related topics - some recent developments and results'', Proc. Int. Congr. Math., Kyoto/Japan 1990, Vol. II, 1561--1571 (1991; Zbl 0746.90019)], and (ii) a characterization of metrics \(d\) on te…
reviewed by: Ortrud R. Oellermann
Mathematics Subject Classification ID: 05C12
Mathematics Subject Classification ID: 05C21
zbMATH DE Number: 5645375
zbMATH Keywords: tight spans
zbMATH Keywords: metrics
zbMATH Keywords: multicommodity flows
zbMATH Keywords: polyhedral combinatorics
MaRDI profile type: Publication
OpenAlex ID: W2123783074
cites work: Hereditary modular graphs
cites work: A characterization of minimizable metrics in the multifacility location problem
cites work: A \(T_X\)-approach to some results on cuts and metrics
cites work: Graphs of some CAT(0) complexes
cites work: Q4124571
cites work: Generosity Helps or an 11-Competitive Algorithm for Three Servers
cites work: Tropical convexity
cites work: Geometry of cuts and metrics
cites work: Trees, tight extensions of metric spaces, and the cohomological dimension of certain groups: A note on combinatorial properties of metric spaces
cites work: Q5514188
cites work: Characterization of the distance between subtrees of a tree by the associated tight span
cites work: On tight spans for directed distances
cites work: Multi-Commodity Network Flows
cites work: Q5629416
cites work: Six theorems about injective metric spaces
cites work: Polyhedra related to undirected multicommodity flows
cites work: Q4011256
cites work: Minimum 0-extensions of graph metrics
cites work: Metrics with finite sets of primitive extensions
cites work: Combinatorial approaches to multiflow problems
cites work: On some connectivity properties of Eulerian graphs
cites work: Combinatorial optimization. Polyhedra and efficiency (3 volumes)
cites work: State of the Art—Location on Networks: A Survey. Part II: Exploiting Tree Network Structure
cites work: Lectures on Polytopes
DOI: 10.1016/J.JCTB.2009.03.001
description: scientific article; zbMATH DE number 5645375