DOI: 10.1142/S0129054111008544

July 19, 2011 14:12 WSPC/INSTRUCTION FILE S0129054111008544

International Journal of Foundations of Computer Science

Vol. 22, No. 5 (2011) 1019–1034 c© World Scientific Publishing Company

A DISTRIBUTED APPROXIMATION ALGORITHM FOR

FAULT-TOLERANT METRIC FACILITY LOCATION

SHIHONG XU

School of Computer Science

University of Adelaide

Adelaide, SA 5005, Australia shihong.xu@adelaide.edu.au

HONG SHEN

School of Computer Science

University of Adelaide

Adelaide, SA 5005, Australia hong.shen@adelaide.edu.au http://www.cs.adelaide.edu.au/˜hong

Received 1 March 2010

Accepted 20 June 2010

Communicated by Akihiro Fujiwara

In this paper, we propose an approximation algorithm for the Fault-Tolerant Metric

Facility Location problem which can be implemented in a distributed and asynchronous manner within O(n) rounds of communication, where n is the number of vertices in the network. Given a constant size set R which represents distinct levels of fault-tolerant requirements of all cities, as well as the two-part (facility and connection) cost of the optimal solution, i.e. F ∗+C∗, the cost of our solution is no more than |R| ·F ∗+2C∗ for the general case, and less than F ∗+2C∗ for the special case where all cities have a uniform connectivity requirement. Extensive numerical experiments showed that the quality of our solutions is comparable (within 4% error) to the optimal solution in practice.

Keywords: Approximation algorithms; distributed algorithms; fault tolerance; metric facility location problem. 1. Introduction

Uncapacitated Facility Location (UFL) [18] is one the a classical problem that has been widely studied in operations research. In this problem, we are given a set of facilities F and a set of cities C. For every facility i ∈ F , a non-negative number fi is given as the opening cost of facility i; and for every facility-city pair (i, j) a connection cost cij between facility i and city j ∈ C. The objective of the problem is to open a subset of the facilities in F , and connect each city to an open facility so that the total cost is minimized. In UFL, only one connection is required for each city which is not the case in many application scenarios and therefore researchers 1019

In t.

J.

Fo un d.

C om pu t.

Sc i. 20 11 .2 2: 10 19 -1 03 4.

D ow nl oa de d fro m w w w .w or ld sc ie nt ifi c.c om by

C

H

IN

ES

E

U

N

IV

ER

SI

TY

O

F

H

O

N

G

K

O

N

G o n 02 /0 6/ 15 . F or p er so na l u se o nl y.

July 19, 2011 14:12 WSPC/INSTRUCTION FILE S0129054111008544 1020 S. Xu & H. Shen extend the problem by proposing Fault-Tolerant Facility Location (FTFL) [13]. In

FTFL, each city j ∈ C has a connectivity requirement rj and has to be assigned to rj distinct facilities instead of just one, to achieve fault-tolerance capability in case of a connection or facility fails. The FTFL problem has been studied extensively in the recent years [13, 7, 8, 9, 21] and in this paper, we studied the metric version of the FTFL problem, where connection costs follow triangle inequality. An example of the problem is illustrated in Fig. 1 where three cities are to be connected with two facilities. It is clear that the optimal solution is to open both facility and connected facility pairs as illustrated because the second city requires two connections. The minimum cost is 8. The problem becomes UFL problem if cities require one facillity for each and it is not hard to see that the optimal solution is to open one facility and the minimum cost is 5. f1 f2 r1 = 1 r2 = 2 r3 = 1 c11 c12 c22 c23 c21 c13 f1 = f2 = 2, r1 = r3 = 1, r2 = 2 c11 = c12 = c13 = c21 = c22 = c23 = 1

Optimal solution with minimum cost 8: y1 = y2 = 1, x11 = x12 = x22 = x23 = 1

Fig. 1. An example of FTFL problem.

Aside from industrial facility placement and fault-tolerant network design, FTFL also found application in content distribution for parallel access (see our early work [22]). With popular contents distributed over the network (like Content Distributed

Network), researcher has proposed parallel-access scheme to retrieve files from multiple sources to accelerate application performance. In such an application, the traditional content distribution policy which is optimized for single-access is not necessary optimal and therefore how to place (distribute) contents over the network to facilitate parallel access becomes a research topic. Actually, it is not hard to see that the problem of placing an object across the network for parallel access is similar to the problem of placing industrial facilities to achieve fault-tolerant capability as in the FTFL problem.

For an application like content distribution, it is essential to develop distributed algorithms to work in a network environment lack of global knowledge: global state information is either impractical to be collected or will be outdated when it is ready to be used. A distributed algorithm is also helpful to offload the central server and reduce the amount of data transferring in the network. Since the NP-hardness of the problem, we proposed an approximation algorithm which is implemented in a

In t.

J.

Fo un d.

C om pu t.

Sc i. 20 11 .2 2: 10 19 -1 03 4.

D ow nl oa de d fro m w w w .w or ld sc ie nt ifi c.c om by

C

H

IN

ES

E

U

N

IV

ER

SI

TY

O

F

H

O

N

G

K

O

N

G o n 02 /0 6/ 15 . F or p er so na l u se o nl y.

July 19, 2011 14:12 WSPC/INSTRUCTION FILE S0129054111008544

A Distributed Approximation Algorithm for Fault-Tolerant Metric Facility Location 1021 distributed and asynchronous manner in the paper. Our algorithm could be regarded as an extension of the JMS Algorithm which solves the fault-tolerant version of the problem in a distributed environment. Our algorithm follows the same greedy heuristic approach as the JMS Algorithm, i.e. to find the most cost-efficient star repeatedly in each iteration, but allows multiple connections for each city. The feature of our algorithm is its distributed implementation and asynchronous manner of communication which is suitable for an environment lack of global knowledge. The algorithm can be completed within O(n) round of communication in the CONGEST model, where a reasonable bound—O(log n) bits, is imposed on each message size.