Please use this identifier to cite or link to this item: http://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.
RMID: 0020121077
Published version: http://crpit.com/abstracts/CRPITV128Liao.html
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.