Please use this identifier to cite or link to this item:
https://hdl.handle.net/2440/77277
Type: | Conference paper |
Title: | Approximating the reliable resource allocation problem using inverse dual fitting |
Author: | Liao, K. Shen, H. |
Citation: | Proceedings of Computing, the Australasian Theory Symposium, held in Melbourne, January-February, 2012: pp.75-82 |
Publisher: | Australian Computer Society, Inc |
Publisher Place: | Australia |
Issue Date: | 2012 |
Series/Report no.: | Conferences in Research and Practice in Information Technology; 128 |
ISBN: | 9781921770098 |
ISSN: | 1445-1336 |
Conference Name: | Computing: The Australasian Theory Symposium (18th : 2012 : Melbourne) |
Statement of Responsibility: | 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. |
Published version: | http://crpit.com/abstracts/CRPITV128Liao.html |
Appears in Collections: | Aurora harvest 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.