Note: |
|
(LaTeX) 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. |
URL for the Abstract: |
http://link.springer-ny.com/link/service/journals/00453/contents/01/0080/index.html |
Categories,
Keywords: |
Polynomial-time approximation algorithms, fault-tolerance, redundant assignments |
HyperLinks / References / URLs: |
|
Copyright Message: |
|
Personal Comments: |
|
Download
Access Level: |
Public |
|