Unconstrained and constrained fault-tolerant resource allocation

Kewen Liao, Hong Shen

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

Abstract

First, we study the Unconstrained Fault-Tolerant Resource Allocation (UFTRA) problem (a.k.a. FTFA problem in [19]). In the problem, we are given a set of sites equipped with an unconstrained number of facilities as resources, and a set of clients with set R as corresponding connection requirements, where every facility belonging to the same site has an identical opening (operating) cost and every client-facility pair has a connection cost. The objective is to allocate facilities from sites to satisfy R at a minimum total cost. Next, we introduce the Constrained Fault-Tolerant Resource Allocation (CFTRA) problem. It differs from UFTRA in that the number of resources available at each site i is limited by Ri . Both problems are practical extensions of the classical Fault-Tolerant Facility Location (FTFL) problem [10]. For instance, their solutions provide optimal resource allocation (w.r.t. enterprises) and leasing (w.r.t. clients) strategies for the contemporary cloud platforms. In this paper, we consider the metric version of the problems. For UFTRA with uniform R, we present a star-greedy algorithm. The algorithm achieves the approximation ratio of 1.5186 after combining with the cost scaling and greedy augmentation techniques similar to [3,14], which significantly improves the result of [19] using a phase-greedy algorithm. We also study the capacitated extension of UFTRA and give a factor of 2.89. For CFTRA with uniform R, we slightly modify the algorithm to achieve 1.5186-approximation. For a more general version of CFTRA, we show that it is reducible to FTFL using linear programming.

Original languageEnglish
Title of host publicationComputing and Combinatorics - 17th Annual International Conference, COCOON 2011, Proceedings
EditorsBin Fu, Ding-Zhu Du
PublisherSpringer Berlin
Pages555-566
Number of pages12
Volume6842
ISBN (Electronic)9783642226854
ISBN (Print)9783642226847
DOIs
Publication statusPublished - 2011
Externally publishedYes
Event17th Annual International Computing and Combinatorics Conference, COCOON 2011 - Dallas, TX, United States
Duration: 14 Aug 201116 Aug 2011

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6842 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference17th Annual International Computing and Combinatorics Conference, COCOON 2011
CountryUnited States
CityDallas, TX
Period14/08/1116/08/11

Fingerprint Dive into the research topics of 'Unconstrained and constrained fault-tolerant resource allocation'. Together they form a unique fingerprint.

Cite this