TY - JOUR
T1 - LP-based approximation algorithms for reliable resource allocation
AU - Liao, Kewen
AU - Shen, Hong
PY - 2014/1/1
Y1 - 2014/1/1
N2 - We initiate the study of the reliable resource allocation (RRA) problem. In this problem, we are given a set of sites ℱ each with an unconstrained number of facilities as resources. Every facility at site i ∈ ℱ has an opening cost and a service reliability pi. There is also a set of clients C to be allocated to facilities. Every client j ∈ C accesses a facility at i with a connection cost and reliability lij. In addition, every client j has a minimum reliability requirement (MRR) r j for accessing facilities. The objective of the problem is to decide the number of facilities to open at each site and connect these facilities to clients such that all clients' MRRs are satisfied at a minimum total cost. The unconstrained fault-tolerant resource allocation problem studied in Liao and Shen [(2011) Unconstrained and Constrained Fault-Tolerant Resource Allocation. Proceedings of the 17th Annual International Conference on Computing and Combinatorics (COCOON), Dallas, Texas, USA, August 14-16, pp. 555-566. Springer, Berlin] is a special case of RRA. Both of these resource allocation problems are derived from the classical facility location theory. In this paper, for solving the general RRA problem, we develop two equivalent primal-dual algorithms where the second one is an acceleration of the first and runs in quasi-quadratic time. In the algorithm's ratio analysis, we first obtain a constant approximation factor of 2+2√2 and then a reduced ratio of 3.722 using a factor revealing program, when lij's are uniform on i (partially uniform) and rj's are uniform above the threshold reliability that a single access to a facility is able to provide. The analysis further elaborates and generalizes the inverse dual-fitting technique introduced in Xu and Shen [(2009) The Fault-Tolerant Facility Allocation Problem. Proceedings of the 20th International Symposium on Algorithms and Computation (ISAAC), Honolulu, HI, USA, December 16-18, pp. 689-698. Springer, Berlin]. Moreover, we formalize this technique for analyzing the minimum set cover problem. For a special case of RRA, where all rj's and l ij's are uniform, we derive its approximation ratio through a novel reduction to the uncapacitated facility location problem. The reduction demonstrates some useful and generic linear programming techniques.
AB - We initiate the study of the reliable resource allocation (RRA) problem. In this problem, we are given a set of sites ℱ each with an unconstrained number of facilities as resources. Every facility at site i ∈ ℱ has an opening cost and a service reliability pi. There is also a set of clients C to be allocated to facilities. Every client j ∈ C accesses a facility at i with a connection cost and reliability lij. In addition, every client j has a minimum reliability requirement (MRR) r j for accessing facilities. The objective of the problem is to decide the number of facilities to open at each site and connect these facilities to clients such that all clients' MRRs are satisfied at a minimum total cost. The unconstrained fault-tolerant resource allocation problem studied in Liao and Shen [(2011) Unconstrained and Constrained Fault-Tolerant Resource Allocation. Proceedings of the 17th Annual International Conference on Computing and Combinatorics (COCOON), Dallas, Texas, USA, August 14-16, pp. 555-566. Springer, Berlin] is a special case of RRA. Both of these resource allocation problems are derived from the classical facility location theory. In this paper, for solving the general RRA problem, we develop two equivalent primal-dual algorithms where the second one is an acceleration of the first and runs in quasi-quadratic time. In the algorithm's ratio analysis, we first obtain a constant approximation factor of 2+2√2 and then a reduced ratio of 3.722 using a factor revealing program, when lij's are uniform on i (partially uniform) and rj's are uniform above the threshold reliability that a single access to a facility is able to provide. The analysis further elaborates and generalizes the inverse dual-fitting technique introduced in Xu and Shen [(2009) The Fault-Tolerant Facility Allocation Problem. Proceedings of the 20th International Symposium on Algorithms and Computation (ISAAC), Honolulu, HI, USA, December 16-18, pp. 689-698. Springer, Berlin]. Moreover, we formalize this technique for analyzing the minimum set cover problem. For a special case of RRA, where all rj's and l ij's are uniform, we derive its approximation ratio through a novel reduction to the uncapacitated facility location problem. The reduction demonstrates some useful and generic linear programming techniques.
KW - approximation algorithms
KW - inverse dual fitting
KW - reduction
KW - reliable resource allocation
KW - time complexity
UR - http://www.scopus.com/inward/record.url?scp=84891526908&partnerID=8YFLogxK
U2 - 10.1093/comjnl/bxs164
DO - 10.1093/comjnl/bxs164
M3 - Article
AN - SCOPUS:84891526908
VL - 57
SP - 154
EP - 164
JO - Computer Journal
JF - Computer Journal
SN - 0010-4620
IS - 1
ER -