Abstract
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.
Original language | English |
---|---|
Title of host publication | Theory of Computing 2012 - Proceedings of the Eighteenth Computing |
Subtitle of host publication | The Australasian Theory Symposium, CATS 2012 |
Editors | Juli´an Mestre |
Pages | 75-82 |
Number of pages | 8 |
Volume | 128 |
Publication status | Published - 24 Jul 2012 |
Externally published | Yes |
Event | Theory of Computing 2012 - 18th Computing: The Australasian Theory Symposium, CATS 2012 - Melbourne, VIC, Australia Duration: 31 Jan 2012 → 3 Feb 2012 |
Conference
Conference | Theory of Computing 2012 - 18th Computing: The Australasian Theory Symposium, CATS 2012 |
---|---|
Country/Territory | Australia |
City | Melbourne, VIC |
Period | 31/01/12 → 3/02/12 |