# Item

ITEM ACTIONSEXPORT

Released

Journal Article

#### Minimum Congestion Redundant Assignments to Tolerate Random Faults

##### MPS-Authors

##### Locator

There are no locators available

##### Fulltext (public)

There are no public fulltexts available

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Fotakis, D., & Spirakis, P. G. (2002). Minimum Congestion Redundant Assignments
to Tolerate Random Faults.* Algorithmica,* *32*, 396-422.

Cite as: http://hdl.handle.net/11858/00-001M-0000-000F-2FEE-4

##### 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.