de.mpg.escidoc.pubman.appbase.FacesBean
English
 
Help Guide Disclaimer Contact us Login
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Journal Article

Minimum Congestion Redundant Assignments to Tolerate Random Faults

MPS-Authors
http://pubman.mpdl.mpg.de/cone/persons/resource/persons44436

Fotakis,  Dimitris
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons45532

Spirakis,  Paul G.
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

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.