research unit 1

This site is powered by Aigaion - A PHP/Web based management system for shared and annotated bibliographies. For more information visit


Type of publication:Article
Entered by:
TitleMinimum Congestion Redundant Assignments to Tolerate Random Faults
Bibtex cite IDRACTI-RU1-2002-12
Journal Algorithmica
Year published 2002
Volume 32
Number 3
Pages 396-422
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 ci and failing independently with probability fi. We are also given a set M of messages to be delivered over K, and a fault-tolerance constraint (1 - å), and we seek a redundant assignment ö that minimizes congestion Cong(ö), i.e. the maximum channel load, subject to the constraint that, with probability no less than (1 - e), 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[ln(|K|/å)/ln(1/fmax)]-approximation algorithm for related capacity channels and unit size messages. Both algorithms are based on computing a collection (K1,., Kí of disjoint channel subsets such that, with probability no less than (1 - å), 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+o(1))-approximation algorithm for arbitrary capacities.
Fotakis, Dimitris
Spirakis, Paul
faults_algorithmica.pdf (main file)
Publication ID296