Improved approximation algorithms for constrained fault-tolerant resource allocation (Extended abstract)

Kewen Liao, Hong Shen, Longkun Guo

Research output: Chapter in Book/Report/Conference proceedingConference Paper published in Proceedings

Abstract

In Constrained Fault-Tolerant Resource Allocation (FTRA) problem, we are given a set of sites containing facilities as resources and a set of clients accessing these resources. Each site i can open at most Ri facilities with opening cost fi. Each client j requires an allocation of r j open facilities and connecting j to any facility at site i incurs a connection cost cij. The goal is to minimize the total cost of this resource allocation scenario. FTRA generalizes the Unconstrained Fault-Tolerant Resource Allocation (FTRA) [10] and the classical Fault-Tolerant Facility Location (FTFL) [7] problems: for every site i, FTRA does not have the constraint Ri , whereas FTFL sets Ri = 1. These problems are said to be uniform if all r j 's are the same, and general otherwise. For the general metric FTRA, we first give an LP-rounding algorithm achieving an approximation ratio of 4. Then we show the problem reduces to FTFL, implying the ratio of 1.7245 from [2]. For the uniform FTRA, we provide a 1.52-approximation primal-dual algorithm in O(n4) time, where n is the total number of sites and clients.

Original languageEnglish
Title of host publicationFundamentals of Computation Theory - 19th International Symposium, FCT 2013, Proceedings
EditorsLeszek Gąsieniec, Frank Wolter
PublisherSpringer-Verlag London Ltd.
Pages236-247
Number of pages12
Volume8070
ISBN (Electronic)9783642401640
ISBN (Print)9783642401633
DOIs
Publication statusPublished - 3 Sep 2013
Externally publishedYes
Event19th International Symposium on Fundamentals of Computation Theory, FCT 2013 - Liverpool, United Kingdom
Duration: 19 Aug 201321 Aug 2013

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8070 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference19th International Symposium on Fundamentals of Computation Theory, FCT 2013
CountryUnited Kingdom
CityLiverpool
Period19/08/1321/08/13

Fingerprint Dive into the research topics of 'Improved approximation algorithms for constrained fault-tolerant resource allocation (Extended abstract)'. Together they form a unique fingerprint.

  • Cite this

    Liao, K., Shen, H., & Guo, L. (2013). Improved approximation algorithms for constrained fault-tolerant resource allocation (Extended abstract). In L. Gąsieniec, & F. Wolter (Eds.), Fundamentals of Computation Theory - 19th International Symposium, FCT 2013, Proceedings (Vol. 8070, pp. 236-247). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8070 LNCS). Springer-Verlag London Ltd.. https://doi.org/10.1007/978-3-642-40164-0_23