Journal Article @Article Artikel in Fachzeitschrift
 Show entries of: this year (2019) | last year (2018) | two years ago (2017) | Notes URL
 Action: login to update Options: Goto entry point

 Author, Editor(s)
 Author(s): Fotakis, Dimitris Spirakis, Paul G. dblp dblp Not MPG Author(s): Spirakis, Paul G.
 BibTeX cite key*: FS2002a

 Title
 Title*: Minimum Congestion Redundant Assignments to Tolerate Random Faults Attachment(s): faults.ps (343.06 KB)

 Journal

 Publisher
 Publisher's Name: Springer Publisher's URL: http://www.springer.de/ Publisher's Address: New York, USA ISSN: 0178-4617

 Vol, No, pp, Date
 Volume*: 32 Number: 3 Publishing Date: 2002 Pages*: 396-422 Number of VG Pages: Page Start: Page End: Sequence Number: DOI:

 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

 Correlation
 MPG Unit: Max-Planck-Institut für Informatik MPG Subunit: Algorithms and Complexity Group Appearance: MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort

BibTeX Entry:

@ARTICLE{FS2002a,
AUTHOR = {Fotakis, Dimitris and Spirakis, Paul G.},
TITLE = {Minimum Congestion Redundant Assignments to Tolerate Random Faults},
JOURNAL = {Algorithmica},
PUBLISHER = {Springer},
YEAR = {2002},
NUMBER = {3},
VOLUME = {32},
PAGES = {396--422},