TY - GEN

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

AU - Liao, Kewen

AU - Shen, Hong

AU - Guo, Longkun

PY - 2013/9/3

Y1 - 2013/9/3

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84883146292&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-40164-0_23

DO - 10.1007/978-3-642-40164-0_23

M3 - Conference Paper published in Proceedings

AN - SCOPUS:84883146292

SN - 9783642401633

VL - 8070

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 236

EP - 247

BT - Fundamentals of Computation Theory - 19th International Symposium, FCT 2013, Proceedings

A2 - Gąsieniec, Leszek

A2 - Wolter, Frank

PB - Springer-Verlag London Ltd.

T2 - 19th International Symposium on Fundamentals of Computation Theory, FCT 2013

Y2 - 19 August 2013 through 21 August 2013

ER -