Unconstrained and Constrained Fault-Tolerant Resource Allocation

Details Unconstrained and Constrained Fault-Tolerant Resource Allocation Unconstrained and Constrained Fault-Tolerant Resource Allocation

2011-06-12

arxiv.org/abs/1106.2294v1

Computer Science

Data Structures and Algorithms

Scientific paper

First, we study the Unconstrained Fault-Tolerant Resource Allocation (UFTRA) problem (a.k.a. FTFA problem in \cite{shihongftfa}). 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 $\mathcal{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 $\mathcal{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 $R_{i}$. Both problems are practical extensions of the classical Fault-Tolerant Facility Location (FTFL) problem \cite{Jain00FTFL}. 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 $\mathcal{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 \cite{Charikar051.7281.853,Mahdian021.52}, which significantly improves the result of \cite{shihongftfa} using a phase-greedy algorithm. We also study the capacitated extension of UFTRA and give a factor of 2.89. For CFTRA with uniform $\mathcal{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.

Affiliated with

Also associated with

No associations

Rating

Unconstrained and Constrained Fault-Tolerant Resource Allocation does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Unconstrained and Constrained Fault-Tolerant Resource Allocation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Unconstrained and Constrained Fault-Tolerant Resource Allocation will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-712389