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:Inproceedings
Entered by:
TitleEfficient Redundant Assignments under Fault-Tolerance Constraints
Bibtex cite IDRACTI-RU1-1999-8
Booktitle Randomization, Approximation, and Combinatorial Algorithms and Techniques (RANDOM-APPROX)
Year published 1999
Pages 156-167
We consider the problem of computing minimum congestion, fault-tolerant, redundant assignments of messages to faulty parallel de- livery channels. In particular, we are given a set M of faulty channels, each having an integer capacity ci and failing independently with proba- bility fi. We are also given a set of messages to be delivered over M, 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 􀀀 ), all the messages have a copy on at least one active channel. We present a 4-approximation algorithm for identical capacity channels and arbitrary message sizes, and a 2l ln(jMj=) ln(1=fmax)m-approximation algorithm for related capacity channels and unit size messages. Both algorithms are based on computing a collection of disjoint chan- nel 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 present a 2-approximation algorithm for identical capacities, and a (8 + o(1))-approximation algorithm for arbitrary ca- pacities.
Fotakis, Dimitris
Spirakis, Paul
S16_APPROX_1999.pdf (main file)
Publication ID372