Please use this identifier to cite or link to this item:
Scopus Web of Science® Altmetric
Type: Journal article
Title: LP-based approximation algorithms for reliable resource allocation
Author: Liao, K.
Shen, H.
Citation: The Computer Journal, 2014; 57(1):154-164
Publisher: Oxford University Press (OUP)
Issue Date: 2014
ISSN: 0010-4620
Statement of
Kewen Liao and Hong Shen
Abstract: 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 to be allocated to facilities. Every client j ∈ accesses a facility at i with a connection cost and reliability lij. In addition, every client j has a minimum reliability requirement (MRR) rj 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 lij'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.
Keywords: reliable resource allocation; approximation algorithms; time complexity; inverse dual fitting; reduction
Rights: © The Author 2013. Published by Oxford University Press on behalf of The British Computer Society. All rights reserved
DOI: 10.1093/comjnl/bxs164
Appears in Collections:Aurora harvest 7
Computer Science publications

Files in This Item:
There are no files associated with this item.

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.