Combinatorial approaches to multiflow problems

Let V be a finite set and denote by (V) and [V] the sets of all ordered and unordered pairs (x,y) and [x,y] (x,y\(\in V)\). A multiflow is a family \(F=\{f_ u| u\in U\}\) where \(U\subseteq [V]\) and for \(u=[s,t]\) \(f_ u\) is a flow with terminals s and t (i.e. either a flow from s to t or from t to s) in the complete directed graph \(G=(V,(V)).\) Define \(\zeta_ F\), \(\delta_ F\in {\mathbb{R}}_+^{[V]}\) by \[ \zeta_ F[x,y]=\sum \{f(x,y)+f(y,x)| f\in F\}\quad and \] \[ \delta_ F[x,y]=\| f_{[x,y]}\|,\quad if\quad [x,y]\in U,\quad and\quad \delta_ F[x,y]=0,\quad otherwise \] where \(\| f\|\) denotes the value of flow f. The author discusses theoretical properties of the following two problems. (a) The feasibility problem: Given \(c,d\in {\mathbb{R}}_+^{[V]}\), find a multiflow F satisfying (1) \(\zeta_ F\leq c\) and \(\delta_ F\geq d\). (b) A general extremal multiflow problem: Given \(a,b,c,d\in {\mathbb{R}}_+^{[V]}\), find a multiflow F maximizing \(a\delta_ F-b\zeta_ F\) subject to (1). Deriving these results a 'combinatorial' approach is used rather than a 'linear programming' approach.

Recommendations

Cited in

(68)

This page was built for publication: Combinatorial approaches to multiflow problems

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