Please use this identifier to cite or link to this item:
|Scopus||Web of Science®||Altmetric|
|Title:||Fast fault-tolerant resource allocation|
|Citation:||Proceedings: 2011 12th International Conference on Parallel and Distributed Computing, Applications and Technologies: PDCAT 2011: 20-22 October 2011 Gwangju, Korea: pp. 231-236|
|Conference Name:||International Conference on Parallel and Distributed Computing, Applications and Technologies (12th : 2011 : Gwangju, South Korea)|
|Kewen Liao and Hong Shen|
|Abstract:||We present the first efficient approximation algorithm for the Unconstrained Fault-Tolerant Resource Allocation (UFTRA) problem  with uniform fault tolerance levels. UFTRA is a relaxation of the classical Fault-Tolerant Facility Location problem . Based on the fundamental primal-dual theory , our primal-dual algorithm achieves an approximation ratio of 1.861 while it can be implemented in quasi-linear time. Besides the significant improvement in runtime over all previous work, the solution quality of the algorithm matches the work in  using a phase-greedy algorithm and improves the result of  adopting the linear program rounding technique. Built on this algorithm, we also show that the capacitated UFTRA (CUFTRA) problem introduced in  achieves 3.722-approximation in quasi-linear time. In this paper, before the presence of the main algorithm and its extensive theoretical analysis, we provide some necessary background knowledge of the problem. This includes the problem's mathematical model formulation, the primal-dual theory applied to this formulation, and the problem's abstract system model with its potential application domains such as content distribution networks and cloud computing.|
|Rights:||Copyright © 2011 by The Institute of Electrical and Electronics Engineers, Inc.|
|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.