Please use this identifier to cite or link to this item:
|Title:||Approximating the reliable resource allocation problem using inverse dual fitting|
|Citation:||Proceedings of Computing, the Australasian Theory Symposium, held in Melbourne, January-February, 2012: pp.75-82|
|Publisher:||Australian Computer Society, Inc|
|Series/Report no.:||Conferences in Research and Practice in Information Technology; 128|
|Conference Name:||Computing: The Australasian Theory Symposium (18th : 2012 : Melbourne)|
|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 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 _rst 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.|
|Keywords:||Reliable resource allocation; approximation algorithms; time complexity; inverse dual fitting technique|
|Rights:||Copyright © 2012, Australian Computer Society, Inc. 2012, Australian Computer Society, Inc.|
|Appears in Collections:||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.