TY - GEN
T1 - Approximating the reliable resource allocation problem using inverse dual fitting
AU - Liao, Kewen
AU - Shen, Hong
PY - 2012
Y1 - 2012
N2 - We initiate the study of the Reliable Resource Allocation (RRA) problem. In this problem, we are given a set of sites equipped with an unbounded number of facilities as resources. Each facility has an opening cost and an estimated reliability. There is also a set of clients to be allocated to facilities with corresponding connection costs. Each client has a reliability requirement (RR) for accessing resources. The objective is to open a subset of facilities from sites to satisfy all clients' RRs at a minimum total cost. The Unconstrained Fault-Tolerant Resource Allocation (UFTRA) problem studied in (Liao & Shen 2011) is a special case of RRA. In this paper, we present two equivalent primaldual algorithms for the RRA problem, where the second one is an acceleration of the first and runs in quasi-linear time. If all clients have the same RR above the threshold that a single facility can provide, our analysis of the algorithm yields an approximation factor of 2+2 √2 and later a reduced ratio of 3.722 using a factor revealing program. The analysis further elaborates and generalizes the generic inverse dual fitting technique introduced in (Xu & Shen 2009). As a by-product, we also formalize this technique for the classical minimum set cover problem.
AB - We initiate the study of the Reliable Resource Allocation (RRA) problem. In this problem, we are given a set of sites equipped with an unbounded number of facilities as resources. Each facility has an opening cost and an estimated reliability. There is also a set of clients to be allocated to facilities with corresponding connection costs. Each client has a reliability requirement (RR) for accessing resources. The objective is to open a subset of facilities from sites to satisfy all clients' RRs at a minimum total cost. The Unconstrained Fault-Tolerant Resource Allocation (UFTRA) problem studied in (Liao & Shen 2011) is a special case of RRA. In this paper, we present two equivalent primaldual algorithms for the RRA problem, where the second one is an acceleration of the first and runs in quasi-linear time. If all clients have the same RR above the threshold that a single facility can provide, our analysis of the algorithm yields an approximation factor of 2+2 √2 and later a reduced ratio of 3.722 using a factor revealing program. The analysis further elaborates and generalizes the generic inverse dual fitting technique introduced in (Xu & Shen 2009). As a by-product, we also formalize this technique for the classical minimum set cover problem.
KW - Approximation algorithms
KW - Inverse dual fitting technique
KW - Reliable resource allocation
KW - Time complexity
UR - http://www.scopus.com/inward/record.url?scp=84864020493&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:84864020493
SN - 9781921770098
T3 - Conferences in Research and Practice in Information Technology Series
SP - 75
EP - 82
BT - Theory of Computing 2012 - Proceedings of the Eighteenth Computing
T2 - Theory of Computing 2012 - 18th Computing: The Australasian Theory Symposium, CATS 2012
Y2 - 31 January 2012 through 3 February 2012
ER -