, a weight function
, a capacity
function
, and a requirement function
.
such that, for each edge
e
,
and, for any pair of nodes
i
and
j
, the number of
edge disjoint paths between
i
and
j
is at least
r(i,j)
where, for each
edge
e
,
f(e)
copies of
e
are available.
.
where
R
is the maximum requirement
and, for any
n
,
[
133
].
[
2
].
This problem belongs to the class of problems of finding a minimum-cost
subgraph such that the number of edges crossing each cut is at least a
specified requirement, which is a function
f
of the cut. If
f
is symmetric
and maximal then any problem in this class is approximable within
2R
,
where
R
is the maximum value of
f
over all cuts [
344
].
Viggo Kann