Name
Title | ||
|---|---|---|
Improved Approximation Algorithms for Constrained Fault-Tolerant Resource Allocation - (Extended Abstract). |
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. © 2013 Springer-Verlag. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1007/978-3-642-40164-0_23 | FCT |
Keywords | Field | DocType |
null | Approximation algorithm,Mathematical optimization,Computer science,Fault tolerance,Resource allocation,Constrained optimization | Conference |
Volume | Issue | ISSN |
8070 LNCS | null | 16113349 |
Citations | PageRank | References |
1 | 0.34 | 0 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Kewen Liao | 1 | 51 | 11.16 |
| Hong Shen | 2 | 499 | 52.98 |
| Longkun Guo | 3 | 6 | 5.49 |