Approximating the reliable resource allocation problem using inverse dual fitting

Kewen Liao, Hong Shen

Research output: Chapter in Book/Report/Conference proceedingConference Paper published in Proceedings

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 languageEnglish
Title of host publicationTheory of Computing 2012 - Proceedings of the Eighteenth Computing
Subtitle of host publicationThe Australasian Theory Symposium, CATS 2012
EditorsJuli´an Mestre
Pages75-82
Number of pages8
Volume128
Publication statusPublished - 24 Jul 2012
Externally publishedYes
EventTheory of Computing 2012 - 18th Computing: The Australasian Theory Symposium, CATS 2012 - Melbourne, VIC, Australia
Duration: 31 Jan 20123 Feb 2012

Conference

ConferenceTheory of Computing 2012 - 18th Computing: The Australasian Theory Symposium, CATS 2012
CountryAustralia
CityMelbourne, VIC
Period31/01/123/02/12

Fingerprint Dive into the research topics of 'Approximating the reliable resource allocation problem using inverse dual fitting'. Together they form a unique fingerprint.

Cite this