hide
Free keywords:
-
Abstract:
We consider the problem of computing minimum congestion, fault-tolerant,
redundant assignments of messages to faulty, parallel delivery channels. In
particular, we are given a set $K$ of faulty channels, each having an integer
capacity $c_i$ and failing independently with probability $f_i$. We are also
given a set $M$ of messages to be delivered over $K$, and a fault-tolerance
constraint $(1-\epsilon)$, and we seek a redundant assignment $\phi$; that
minimizes congestion ${\sf Cong}(\phi)$, i.e. the maximum channel load, subject
to the constraint that, with probability no less than $(1-\epsilon)$, all the
messages have a copy on at least one active channel. We present a
polynomial-time 4-approximation algorithm for identical capacity channels and
arbitrary message sizes, and a $2 \lceil \ln(|K|/\epsilon)/\ln(1/f_{{\rm max}})
\rceil$-approximation algorithm for related capacity channels and unit size
messages.
Both algorithms are based on computing a collection $\{K_1, \ldots, K_\nu\}$ of
disjoint channel subsets such that, with probability no less than (1-\epsilon),
at least one channel is active in each subset. The objective is to maximize the
sum of the minimum subset capacities. Since the exact version of this problem
is NP-complete, we provide a 2-approximation algorithm for identical
capacities, and a polynomial-time $(8+{\rm o}(1))$-approximation algorithm for
arbitrary capacities.
