Indexed by:
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 R-i facilities with opening cost f(i). Each client j requires an allocation of r(j) open facilities and connecting j to any facility at site i incurs a connection cost c(ij). The goal is to minimize the total cost of this resource allocation scenario. FTRA generalizes the Unconstrained Fault-Tolerant Resource Allocation (FTRA(infinity)) [1] and the classical Fault-Tolerant Facility Location (FTFL) [2] problems: for every site i, FTRA(infinity) does not have the constraint R-i, whereas FTFL sets R-i = 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 [3]. For the uniform FTRA, we provide a 1.52-approximation primal-dual algorithm in O (n(4)) time, where n is the total number of sites and clients. (C) 2015 Elsevier B.V. All rights reserved.
Keyword:
Reprint 's Address:
Version:
Source :
THEORETICAL COMPUTER SCIENCE
ISSN: 0304-3975
Year: 2015
Volume: 590
Page: 118-128
0 . 6 4 3
JCR@2015
0 . 9 0 0
JCR@2023
ESI Discipline: COMPUTER SCIENCE;
ESI HC Threshold:175
JCR Journal Grade:3
CAS Journal Grade:4
Cited Count:
WoS CC Cited Count: 1
SCOPUS Cited Count: 2
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 0
Affiliated Colleges: