---
res:
bibo_abstract:
- 'An elementary h-route ow, for an integer h 1, is a set of h edge- disjoint paths
between a source and a sink, each path carrying a unit of ow, and an h-route ow
is a non-negative linear combination of elementary h-routeows. An h-route cut
is a set of edges whose removal decreases the maximum h-route ow between a given
source-sink pair (or between every source-sink pair in the multicommodity setting)
to zero. The main result of this paper is an approximate duality theorem for multicommodity
h-route cuts and ows, for h 3: The size of a minimum h-route cut is at least f=h
and at most O(log4 k f) where f is the size of the maximum h-routeow and k is
the number of commodities. The main step towards the proof of this duality is
the design and analysis of a polynomial-time approximation algorithm for the minimum
h-route cut problem for h = 3 that has an approximation ratio of O(log4 k). Previously,
polylogarithmic approximation was known only for h-route cuts for h 2. A key ingredient
of our algorithm is a novel rounding technique that we call multilevel ball-growing.
Though the proof of the duality relies on this algorithm, it is not a straightforward
corollary of it as in the case of classical multicommodity ows and cuts. Similar
results are shown also for the sparsest multiroute cut problem.@eng'
bibo_authorlist:
- foaf_Person:
foaf_givenName: Petr
foaf_name: Kolman, Petr
foaf_surname: Kolman
- foaf_Person:
foaf_givenName: Christian
foaf_name: Scheideler, Christian
foaf_surname: Scheideler
foaf_workInfoHomepage: http://www.librecat.org/personId=20792
bibo_doi: 10.1007/s00224-013-9454-3
bibo_issue: '2'
dct_date: 2013^xs_gYear
dct_publisher: Springer@
dct_title: 'Towards Duality of Multicommodity Multiroute Cuts and Flows: Multilevel
Ball-Growing@'
...