Please use this identifier to cite or link to this item:
Scopus Web of Science® Altmetric
Type: Conference paper
Title: Fast fault-tolerant resource allocation
Author: Liao, K.
Shen, H.
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
Publisher: IEEE
Publisher Place: USA
Issue Date: 2011
ISBN: 9780769545646
Conference Name: International Conference on Parallel and Distributed Computing, Applications and Technologies (12th : 2011 : Gwangju, South Korea)
Statement of
Kewen Liao and Hong Shen
Abstract: We present the first efficient approximation algorithm for the Unconstrained Fault-Tolerant Resource Allocation (UFTRA) problem [13] with uniform fault tolerance levels. UFTRA is a relaxation of the classical Fault-Tolerant Facility Location problem [11]. Based on the fundamental primal-dual theory [25], 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 [28] using a phase-greedy algorithm and improves the result of [29] adopting the linear program rounding technique. Built on this algorithm, we also show that the capacitated UFTRA (CUFTRA) problem introduced in [13] 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.
DOI: 10.1109/PDCAT.2011.41
Appears in Collections:Aurora harvest 5
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.