Fault-Tolerant Facility Location CHAITANYA SWAMY University of Waterloo AND DAVID B. SHMOYS Cornell University Abstract. We consider a fault-tolerant generalization of the classical uncapacitated facility location problem, where each client j has a requirement that r j distinct facilities serve it, instead of just one. We give a 2.076-approximation algorithm for this problem using LP rounding, which is currently the best-known performance guarantee. Our algorithm exploits primal and dual complementary slackness conditions and is based on clustered randomized rounding. A technical difficulty that we overcome is the presence of terms with negative coefficients in the dual objective function, which makes it difficult to bound the cost in terms of dual variables. For the case where all requirements are the same, we give a primal-dual 1.52-approximation algorithm. We also consider a fault-tolerant version of the k-median problem. In the metric k-median problem, we are given n points in a metric space. We must select k of these to be centers, and then assign each input point j to the selected center that is closest to it. In the fault-tolerant version we want j to be assigned to rj distinct centers. The goal is to select the k centers so as to minimize the sum of assignment costs. The primal-dual algorithm for fault-tolerant facility location with uniform requirements also yields a 4-approximation algorithm for the fault-tolerant k-median problem for this case. This the first constant-factor approximation algorithm for the uniform requirements case. Categories and Subject Descriptors: F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems—Computations on discrete structures General Terms: Algorithms, Theory Additional Key Words and Phrases: Approximation algorithms, facility location, k-median problem A preliminary version of this article [Swamy and Shmoys 2003] appeared in the Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). C. Swamy’s research was supported partially by NSF grant CCR-9912422, and carried out while he was a graduate student at the Department of Computer Science, Cornell University, Ithaca, NY 14853. D. B. Shmoys was supported in part by NSF grants CCR-9912422, CCF-0430682 and DMI-0500263. Authors’ addresses: C. Swamy, Department of Combinatorics and Optimization, University of Waterloo, 200 University Avenue West, Waterloo, ON N2L 3G1, Canada, e-mail: cswamy@math. uwaterloo.ca; D. B. Shmoys, School of ORIE and Department of Computer Science, Cornell University, Ithaca, NY 14853, e-mail: shmoys@cs.cornell.edu. Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or direct commercial advantage and that copies show this notice on the first page or initial screen of a display along with the full citation. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, to redistribute to lists, or to use any component of this work in other works requires prior specific permission and/or a fee. Permissions may be requested from Publications Dept., ACM, Inc., 2 Penn Plaza, Suite 701, New York, NY 10121-0701 USA, fax +1 (212) 869-0481, or permissions@acm.org. C 2008 ACM 1549-6325/2008/08-ART51 $5.00 DOI 10.1145/1383369.1383382 http://doi.acm.org/ 10.1145/1383369.1383382 51 51:2 C. SWAMY AND D. B. SHMOYS ACM Reference Format: Swamy, C. and Shmoys, D. B. 2008. Fault-tolerant facility location. ACM Trans. Algor. 4, 4, Article 51 (August 2008), 27 pages. DOI = 10.1145/1383369.1383382 http://doi.acm.org/10.1145/ 1383369.1383382 1. Introduction Facility location is a classical problem that has been widely studied in the field of operations research (see, e.g., the text of Mirchandani and Francis [1990]). In its simplest version, the uncapacitated facility location (UFL) problem, we are given a set of facilities F and a set of clients D. Each facility i has an opening cost fi , and assigning client j to facility i incurs a cost equal to the distance cij between i and j. We want to open a subset of the facilities in F and assign the clients to open facilities so as to minimize the sum of the facility opening costs and client assignment costs. We consider the case where the distances cij form a metric, that is, they are symmetric and satisfy the triangle inequality. In many settings it is essential to provide safeguards against failures by designing fault-tolerant solutions. For example, in a distributed network, we want to place caches and assign data requests to caches so as to be resistant against caches becoming unavailable due to node or link failures. A common solution is to replicate data items across caches and build some resilience in the network. This motivates the fault-tolerant facility location (FTFL) problem, wherein each client j has a requirement r j and has to be assigned to r j distinct facilities instead of just one. Multiple facilities provide a backup against failures; if the facility closest to a client fails, the other facilities assigned to it could be used to serve it. To give a more concrete example, consider a setting where facilities (which could represent caches) fail independently with probability p, and each client j must be guaranteed to be served by a (functional) facility with probability at least qj . Then, this quality-of-service requirement translates precisely to the constraint that each client j be assigned to rj = log(1 − qj )/ log p distinct facilities. A more precise statement of the problem is as follows: We are given a set of facilities F and a set of clients D, and each client j has a requirement rj ≥ 1. Each facility i has, as usual, an opening cost of fi . In any feasible solution, we must assign every client j to rj distinct open facilities. The assignment cost or service cost incurred for j is the sum of the distances from j to these rj facilities. The objective is to open a subset of the facilities, and assign each client j to rj distinct open facilities so as to minimize the total facility opening and client assignment costs. This is a generalization of the uncapacitated facility location problem, which is the setting where rj = 1 for each client j ∈ D. Our main result is a 2.076-approximation algorithm for fault-tolerant facility location. This is currently the best-known guarantee, improving upon the guarantee of 2.408 due to Guha et al. [2003]. If all requirements are equal, we give a 1.52approximation algorithm by building upon the algorithm of Jain et al. [2002] and Mahdian et al. [2006], which matches the current best guarantee for uncapacitated facility location (i.e., the unit requirement case). The previous best approximation guarantee for FTFL with uniform requirements was 1.861 [Mahdian et al. 2006]. We also consider the fault-tolerant version of the k-median problem where, in addition, a bound k is specified on the number of facilities that may be opened. We consider the case where all requirements are equal and give a 4-approximation algorithm for this case. Related Work. The past several years have given rise to a variety of techniques for the design and analysis of approximation algorithms for the metric uncapacitated facility location problem. The first constant-factor approximation algorithm for this problem was due to Shmoys et al. [1997], who gave a 3.16-approximation algorithm using the filtering technique of Lin and Vitter [1992] to round the optimal solution of a linear program. After an improvement by Guha and Khuller [1999], Chudak and Shmoys [2003] gave an LP-rounding-based (1 + 2)-approximation algorithm. e They used information about the structure of optimal primal and dual solutions, and combined randomized rounding and the decomposition results of Shmoys et al. [1997] to get a variant that might be called clustered randomized rounding. Sviridenko [2002] improved the ratio to 1.58. Jain and Vazirani [2001] gave a combinatorial primal-dual 3-approximation algorithm where the LP is used only in the analysis. Mettu and Plaxton [2003] gave a variant of this algorithm (which is not explicitly a primal-dual algorithm) that achieves the same approximation ratio, but runs in linear time. Local search algorithms were first analyzed by Korupolu et al. [2000] and later improved by Charikar and Guha [2005] and Arya et al. [2004]. Jain et al. [2003] gave a greedy algorithm and showed using a dual-fitting analysis that it has an approximation ratio of 1.61. This was improved by Mahdian et al. [2006] to 1.52, which is the best-known guarantee. Charikar et al. [2002] gave the first constant-factor algorithm for the k-median problem based on LP rounding. This was improved in a series of papers [Jain and Vazirani 2001; Charikar and Guha 2005; Jain et al. 2003; Arya et al. 2004] to (3 + ) [Arya et al. 2004]. The fault-tolerant facility location (FTFL) problem was first studied by Jain and Vazirani [2000], who gave a primal-dual algorithm achieving a performance guarantee logarithmic in the largest requirement. Our algorithm is based on LP rounding. We consider the following LP and its dual. min fi yi + cijxij max r j αj − zi i j i j i (FTFL-P) (FTFL-D) such that xij ≥ r j ∀ j such that αj ≤ βij + cij ∀i, j i xij ≤ yi ∀i, j βij ≤ fi + zi ∀i (1) yi ≤ 1 ∀i j αj ,βij,zi ≥ 0 ∀i, j xij,yi ≥ 0 ∀i, j Variable yi indicates whether facility i is open, and xij indicates whether client j is assigned to facility i. An integer solution to the LP corresponds exactly to a solution to our problem. Guha et al. [2003] round the aforesaid primal LP using filtering and the decomposition technique of Shmoys et al. [1997] to get a 3.16-approximation. They also show that a subsequent greedy local improvement postprocessing step reduces the approximation ratio to 2.408. They actually consider a more general version of FTFL where the service cost of a client j is a weighted sum of its distances to the rj facilities to which it is assigned, where the weights are part of the 51:4 C. SWAMY AND D. B. SHMOYS input. Unless otherwise stated, we use fault-tolerant facility location to denote the unweighted (or unit-weighted) version of the problem. In the case where all clients have the same requirement, namely, rj = r, better results are known. Mahdian et al. [2001] showed that their 1.861-approximation algorithm for UFL can be extended to give an algorithm for FTFL with a guarantee of 1.861. Independent of our work, Jain et al. [2003] gave a 1.61-approximation algorithm based on their 1.61-approximation algorithm for UFL. Our Techniques. Our algorithm is also based on LP rounding, but does not use filtering. Instead, it is based on the clustered randomized rounding technique of Chudak and Shmoys [2003]. Our rounding algorithm exploits the optimality properties of the fractional solution by using complementary slackness conditions to bound the cost of the solution, in terms of both the primal and dual optimal solutions. One difficulty in using LP duality to prove an approximation ratio is the presence of − i zi in the dual objective function. As a result, bounding the cost in terms of jrj αj is not enough to prove an approximation guarantee. In general, this is not an easy problem to tackle; for example, this problem also crops up in designing approximation algorithms for the k-median problem, and consequently the only known LP rounding algorithm [Charikar et al. 2002] uses just the optimal primal LP solution. For FTFL, however, complementary slackness allows us to, in effect, get rid of the negative zi ’s by a single pruning phase; since zi > 0 =⇒ yi = 1, we can open all such i’s and charge the opening cost to the LP. Our algorithm also clusters facilities around certain demand points, called cluster centers, and opens at least one facility in each cluster. We do this clustering carefully so as to ensure that each demand j has at least rj open clusters “near” it; the facilities opened from these clusters are used as backup facilities to serve demand j. Each facility i is opened with probability proportional to yi . The randomization step allows us to reduce the service cost, since now for any client j and any set S of facilities that fractionally serve j such that the facility weight i∈ S xij is “large” (i.e., of at least some constant), there is a constant probability that a facility i from S is opened. Various difficulties arise in trying to extend the algorithm of Chudak and Shmoys [2003] to the fault-tolerant setting. To ensure feasibility, we need to open different facilities in different clusters. Also, we want a cluster to (ideally) have a fractional facility weight of 1, so that the cost of opening a facility in this cluster can be charged to the LP cost for opening a facility from this cluster. A small facility weight could force us to incur huge cost (relative to the LP) in opening a facility within the cluster, whereas if a cluster has a facility weight of more than 1 and we open only one facility from the cluster, then we might end up opening less facilities than necessary to satisfy the requirement of each client. However, unlike UFL, once we require clusters to be disjoint, we cannot expect a cluster to have a facility weight of exactly 1 because we generally will unable to partition those facilities fractionally serving a client into disjoint sets with each set having a facility weight of 1. We tackle this problem by introducing another pruning phase before clustering, where we open all facilities i with “large” yi . Hence, in this clustering step we now only consider facilities that have “small” yi ; this allows us to pack a substantial facility weight within a cluster, without exceeding the limit of 1. ACM Transactions on Algorithms, Vol. 4, No. 4, Article 51, Publication date: August 2008. To analyze the algorithm, we view a demand j with requirement rj as being composed of rj copies which have to be connected to distinct facilities. We allot to each copy a set of facilities from among those that fractionally serve j, that is, a subset of {i : xij > 0}, and a unique backup facility. A copy may only be assigned to a facility that is allotted to it, or to its backup facility. Again, to argue feasibility, we have to ensure that a facility is allotted to at most one copy, and we would like to allot to each copy a facility weight of 1. Although it may not be possible to simultaneously satisfy both of these requirements because of the pruning phase, we can allot a substantial facility weight to each copy. Thusly, we can upper-bound the probability of the event that no facility in the allotted set of the copy is open. This results in an approximation ratio of 2.25. To do better, we distribute facilities more evenly among the copies. We use the so-called pipage rounding technique of Ageev and Sviridenko [2004] to essentially derandomize a hypothetical randomized process in which each copy gets an equal allotment of facility weight. This yields a 2.076-approximation algorithm. For the uniform requirement case, we improve the approximation guarantee of 1.861 [Mahdian et al. 2001] to 1.52 by building upon the algorithm of Jain et al. [2002]. The algorithm is analyzed using the dual fitting approach and we arrive at the same factor LP as Jain et al. [2002], thereby obtaining the same performance guarantees. Combined with a greedy improvement heuristic and the analysis in Mahdian et al. [2006], we get a 1.52-approximation algorithm. Using a Lagrangian relaxation technique introduced in Jain and Vazirani [2001] for the k-median version of UFL, we get a 4-approximation algorithm for the fault-tolerant k-median problem with uniform requirements. 2. A Simple 4-Approximation Algorithm We first give a simple 4-approximation algorithm for the fault-tolerant facility location problem. The algorithm does not use filtering, but rather exploits the complementary slackness conditions to bound the cost of the solution in terms of both the primal and dual optimal solutions. Let (x, y) and (α, β, z) be the optimal primal and dual solutions, respectively, and OPT be the common optimal value. The primal slackness conditions are xij > 0 =⇒ αj = βij + cij, yi > 0 =⇒ j βij = fi + zi . The dual slackness conditions are αj > 0 =⇒ i xij = rj , βij > 0 =⇒ xij = yi , and zi > 0 =⇒ yi = 1. We may assume without loss of generality for each client j, αj > 0, so that i xij = rj . Furthermore, for every client j there is at most one facility i such that 0 < xij < yi , and we may assume this to be the farthest facility serving j because we can always “shift” the assignment of j to facilities nearer to j and ensure that this property holds. Like the Chudak-Shmoys (CS) algorithm for UFL [Chudak and Shmoys 2003], our algorithm is based on the observation that the optimal solution is α-close, that is, xij > 0 =⇒ cij ≤ αj . However, one additional difficulty encountered in using LP duality to prove an approximation ratio, which does not arise in the case of UFL, is the presence of the − i zi term in the dual objective function. As a result, bounding the cost in terms of jrj αj is not enough to prove an approximation guarantee. Nevertheless, the additional structure in the primal and dual solutions, resulting from complementary slackness, allows us to circumvent this difficulty; 51:6 C. SWAMY AND D. B. SHMOYS since zi > 0 =⇒ yi =1, we can open all such facilities i and charge the opening cost to the LP. Throughout, we will view a client j with requirement rj as consisting of r j copies, each of which needs to be connected to a distinct facility. We use j(c) to denote the cth copy of j. We use the terms “client” and “demand” interchangeably, and also “assignment cost” and “service cost” interchangeably. The algorithm consists of two phases. Phase 1. First we open all facilities with yi =1. Let L1 be the set of facilities opened. For every client j,if xij > 0 and yi = 1, we connect a copy of j to i. Notice that at most one copy of j is connected to any such facility. Let Lj ={i ∈ L1: xij > 0}and nj =|Lj |be the number of copies of j connected in this phase. Note that nj ≤rj . The following lemma bounds the cost for this phase. LEMMA 2.1. The cost of phase 1 is jnj αj − i zi. PROOF. Each i with zi > 0isin L1 and for any i ∈L1, all clients j with xij > 0 are connected to it. Since xij > 0 =⇒ αj =cij +βij, for any i ∈L1,wehave αj = (cij +βij) = cij + βij = cij + fi +zi . j:xij>0 j:xij>0 j:xij>0 jj:xij>0 The second equality follows, since βij > 0 =⇒ xij = yi = 1 > 0. Since nj =|{i ∈L1: xij > 0}|, the lemma follows by summing over all i ∈L1. Phase 2. This is a simple clustering step. Let rj = rj −nj be the residual requirement of j. Let Fj ={i : yi < 1, xij > 0}be the set of facilities not in L1 that fractionally serve j in (x, y). Let S ={j : rj ≥1}. We will maintain the invariant that yi ≥rj for all j ∈S. We iteratively do the following until i∈Fj S =∅. S1. Choose j ∈S with minimum αj as a cluster center. S2. Order the facilities in Fj by increasing facility cost. We pick M ⊆Fj starting from the first facility in Fj so that i ∈M yi ≥ rj .If i ∈M yi > rj ,we replace the last facility i in M (i.e., the furthest facility from j is i)bytwo “clones” of i, called i1 and i2. Set yi1 =rj − i ∈M\{i} yi , yi2 =yi −yi1.For each client k (including j) with xik > 0, we set xi1k , xi2k arbitrarily maintaining that xi1k +xi2k = xik, xi1k ≤ yi1 , xi2k ≤ yi2. We include i1 in M,sonow i ∈M yi =rj . S3. Open the rj least expensive facilities in M. For each client k (including j) with Fk ∩M =∅, we connect min(rk , rj ) copies of k to these open facilities, and set rk =rk −min(rk , rj ), Fk =Fk\M. Facilities in M and client j now effectively disappear from the input. Figure 1 shows one iteration of steps S1 through S3. Step S2 is valid since we maintain the invariant that yi ≥rk for all k ∈S. This is clearly true initially, i∈Fk and in any iteration, for any k with Fk ∩M =∅and which lies in S after the iteration, we remove a facility weight of at most rj from Fk , and rk decreases by exactly r j . FIG. 1. One iteration of the clustering step in phase 2. Here, j is the cluster center; 2 copies of j, k, and 1 copy of get connected in this iteration; j and are removed from S after this iteration. We first argue that the algorithm returns a feasible solution. In phase 1, distinct copies get connected to distinct facilities, and no facility with yi = 1 ever gets used in phase 2. In phase 2, we ensure that at most one clone of a facility i is opened. This holds because whenever i ∈ M is replaced by clones, its first clone is not opened in step S3: Since i is included partially in M, it must be the most expensive facility in M and because i ∈M\{i} yi > rj − yi > rj − 1, there are at least rj facilities in M\{i} that are less expensive than i. Hence the clone of i included in M (the first clone) is not opened in step S3. Since only the second clone can be opened whenever a facility is split into clones, at most one clone of a facility is opened. It follows that a client j uses a facility i at most once. Thus, we get a feasible solution where each copy j(c) is connected to a distinct facility. We now bound the cost of the solution obtained. LEMMA 2.2. The facility opening cost in phase 2 is at most i fiyi. PROOF. Facilities are only opened in step S2 of phase 2, where we pick a set of facilities M such that i∈M yi = rj and open the rj least expensive facilities in M. The cost of opening the least expensive facilities is at most rj · (average cost) = i∈M fiyi . Also the facilities in M are not reused. LEMMA 2.3. Let k(c) be a copy of k connected to facility i in phase 2. Then cik ≤ 3αk. PROOF. Let M ⊆ Fj be the set of facilities picked in step S2 such that i ∈ M. Let i be some facility in Fk ∩ M which is nonempty (see Figure 1). Then, cik ≤ ci k + ci j + cij ≤ αk + 2αj . The lemma now follows, since αj ≤ αk because j was chosen as the cluster center and not k (which is in S). THEOREM 2.4. The preceding algorithm delivers a solution of cost at most 4 · OPT. PROOF. The facility cost in phase 2 is at most fi yi ≤ OPT = jrj αj + i ( jnj αj − i zi ). The service cost of j is the service cost for the nj copies 51:8 C. SWAMY AND D. B. SHMOYS connected in phase 1 added to the service cost for the rj copies connected in phase 2. Each copy of j connected in phase 2 incurs a service cost of at most 3αj . So, the total cost is bounded by (cost of phase 1)+(facility cost in phase 2)+(service cost for rj copies in phase 2) ≤ ( jnj αj − i zi ) + fi yi + 3 jrj αj ≤ i 2( jnj αj − i zi ) + 4 jrj αj ≤ 4( jrj αj − i zi ) = 4 · OPT. 3. A Better “Randomized” Algorithm: An Overview We now show that the performance guarantee can be improved substantially by using randomization along with clustering. At a high level, the algorithm proceeds as follows. First we run phase 1 as before, except that we connect a copy of j to i only if xij = 1. The main source of improvement is due to the fact that we open every other facility i with probability proportional to yi . This helps to reduce the service cost, since now for every client j and copy j(c) there is a significant probability that a (distinct) facility with xij > 0 is open. The algorithm is thus in the spirit of the CS algorithm [Chudak and Shmoys 2003], which also uses randomization to reduce the service cost incurred. However, several obstacles have to be overcome to extend the approach to the fault-tolerant setting and thereby prove a good approximation guarantee. We again cluster facilities around demand points, but now each cluster that we create contains a (fractional) facility weight close to 1, and we open at least one facility in the cluster by a randomized process. We will ensure that each demand j has rj clusters “near” it, so that the facilities opened in these clusters, called backup facilities, can be used to serve j without blowing up the service cost by much. This is done by introducing a notion of backup requirement, which is initialized to rj . Whenever we create a cluster, we decrement the backup requirement of all demands j that share a facility with the cluster created. The facility opened in this cluster (which is chosen randomly) serves as a backup facility for each such client j.As long as the backup requirement of j is at least 1, it is a candidate for being chosen as a cluster center; thus at the end, j will share facilities with rj clusters and these provide rj nearby backup facilities. The randomization step, however, causes various technical difficulties. To argue feasibility, we need to open different facilities in different clusters. Also, ideally, we would like each cluster to contain a facility weight of exactly 1. If the facility weight is too small, then we incur a huge cost relative to the LP in opening a facility from the cluster; if the weight is more than 1, then we are using up a fractional facility weight of more than 1 while opening only a single facility, so we might not open enough facilities to satisfy the requirement of a client. In a deterministic setting like that in the 4-approximation algorithm described earlier, we know precisely which facility(ies) is (are) opened within a cluster, and can therefore afford to split facilities across clusters without sacrificing feasibility. Thusly, we can ensure that a cluster contains the “right” amount of facility weight. Guha et al. [2003] also deterministically decide which facility to open within a cluster, possibly splitting a facility across clusters, and thereby relatively easily extend the UFL algorithm of Shmoys et al. [1997] to the fault-tolerant setting. With randomization, on the other hand, any of the facilities in a cluster might get opened. Therefore we cannot now split facilities across clusters, and require that the clusters be disjoint. However, unlike UFL, once we require clusters to be disjoint, we cannot ensure that a cluster has a facility weight of exactly 1. For example, consider a client j with rj = 2 served by three facilities i,i , and i with xij = xi j = xi j = yi = yi = yi = 2; a cluster centered at j consisting of 3 unsplit facilities cannot have a facility weight of exactly 1. We tackle this problem by introducing an intermediate phase 2 (before the clustering step), where we open all facilities i for which yi is “large”; that is, yi is at least some threshold γ, and we connect a copy of j to i if xij ≥ γ. We now work with only the remaining set of facilities and the residual requirements, and perform the aforesaid clustering step. Clearly, we incur a loss of a factor of at most γ due to phase 2. But importantly, since each (remaining) yi <γ, we can now create disjoint clusters and ensure that a cluster contains a facility weight between 1−γand 1. Finally, we open every facility i, be it a cluster facility or a noncluster facility, with probability proportional to yi . To analyze the cost of the solution, we fix a particular way of assigning each copy (that is unassigned after phases 1 and 2) to an open facility, and separately bound the service cost for every copy. For each demand j, we allot to each such copy j(c) a set of preferred facilities P( j(c)), which is a subset of those facilities that fractionally serve the unassigned copies, as well as a distinct backup facility b( j(c)), which is a facility opened from a cluster near j. We assign j(c) to the nearest facility open in P( j(c)) (if there is one) and otherwise to the backup facility b( j(c)). Again, to argue feasibility we require that the preferred sets for the different copies are disjoint. Ideally, we would like to allot a disjoint set of facilities with facility weight 1 to each preferred set, but we face the same difficulty as in forming clusters: It might not be possible to divide the facilities among the different copies so that each copy gets a set with facility weight 1. However, phase 2 ensures that we can allot to each set P( j(c)) a facility weight of at least 1 − γ, which gives a reasonable upper bound on the probability that no facility in P( j(c)) is open. Combining these various components, we thereby obtain an algorithm with a much better approximation ratio of about 2.2, but we can do even better. 3.1. PIPAGE ROUNDING. The final improvement comes by exploiting the pipage rounding technique of Ageev and Sviridenko [2004], which was applied in the context of uncapacitated facility location by Sviridenko [2002]. Suppose that we distribute those facilities serving the unassigned copies of j among the preferred sets and allot to each preferred set a facility weight of 1, perhaps by splitting facilities. A facility i could now lie in multiple preferred sets P( j(c)); let zij(c) be the extent to which facility i is allotted to P( j(c)), so zij(c) = xij. Although the preferred sets c are no longer disjoint, we can still use the aforesaid scheme of opening facilities and assigning copies to facilities as follows: We will make facility i available (for use) to exactly one copy c and with probability zij(c)/xij. So for copy j(c) to be assigned to facility i, it must be that i is open, i is available to copy c, and no facility in P( j(c)) that is nearer to j is available to copy c. So in expectation, each copy j(c) has a facility weight of 1 available to it, and it seems plausible that we should be able to show the probability low of there being an available facility in the preferred set, thereby bounding the expected service cost of the copy. However, there is some dependence between the randomness involved in making a facility available to a copy, and in opening the facility, which makes it difficult to prove a good bound on the expected service cost of a copy. Nevertheless, we will pretend that we have a hypothetical randomized process with various desired properties, writing an expression for the expected cost incurred 51:10 C. SWAMY AND D. B. SHMOYS under this randomized process and bounding this cost. More precisely, we will construct an expression cost(y1,y2,...,yn) that is a function of the yi variables, where n =|F|, satisfying the following properties. P1. When the yi values are set to those values given by the LP optimal solution, we have cost(y1,...,yn) ≤c ·OPT for an appropriate constant c that we will specify later. P2. For any integer solution satisfying certain properties, if we consider the corre sponding {0,1}-setting of the yi values, cost(y1,...,yn) gives an upper bound on the total cost of the integer solution. P3. Furthermore, cost(.) has some nice concavity properties (we will make these precise later). Using property P3, we will argue that, given any initial fractional setting of the yi values, we can obtain a {0,1}-solution y˜ satisfying certain properties, such that cost(y˜1,...,y˜n) ≤cost(y1,...,yn). So, if we set the yi values to those values given by the LP optimal solution to begin with, then properties P1 and P2 show that we obtain an integer solution of cost at most c ·OPT, thereby getting a c-approximation algorithm. Thus, we actually get a deterministic algorithm1 with an approximation guarantee of 2.076. As mentioned earlier, we will obtain expression cost(.) by imagining that we have a randomized process with certain desired properties, and writing out the expected cost incurred under this process. We emphasize that this is for intuitive purposes only; such a randomized process may not exist, and even if it does, we might not know how to implement such a randomized process. 4. Algorithm Details The algorithm runs in three phases which are described in detail next (the entire algorithm is also summarized in Figure 3). Let γ< 1 be a parameter whose value 2 we will fix later. Phase 1. This is very similar to phase 1 of the simple 4-approximation algorithm. Let L1 ={i : yi =1}. We open all facilities in L1. For every client j,if xij =yi =1, we connect a copy of j to i. Let nj be the number of copies of j so connected, and let rj =rj −nj be the residual requirement of j. Phase 2. Open each facility i (in F\L1) with yi ≥ γ. Let L2 be the set of facilities opened. For a client j, we now define Lj ={i : γ ≤xij < 1}. Clearly Lj ⊆L1 ∪L2. Connect min(|Lj |,rj ) copies of j to distinct facilities in Lj . This incurs the loss of a factor of 1 compared to the LP. We ensure that for each j, γ no facility i with xij ≥γ is used after this phase. Let rj =max(rj −|Lj |,0) be the residual requirement of j. Note that xij ≥rj , since if rj > 0, then i:xij<γ rj =rj −|Lj |and rj = i:xij<1 xij. Phase 3. We introduce some notation first. Let Fj denote the set of facilities {i :0 < xij <γ}sorted in order of increasing cij. We define the facility weight of 1This is why the word of randomized appears in quotes in the title of this section. FIG. 2. An iteration of the clustering step in phase 3. a set of facilities S to be facwt(S, j) = i∈S xij. We know that facwt(Fj , j) ≥rj ; we assume without loss of generality that facwt(Fj , j)is exactly r j . (If not, we may simply take a subset of Fj starting from the first facility and proceeding in order until facwt(Fj , j) =rj , where the last facility may only be partially included in Fj .) We describe in the following how to open facilities; once we know the set of open facilities, we assign each client j’s remaining rj copies to the rj open facilities nearest to it to which it is not already assigned. Clustering. Define the backup requirement back( j) =rj . For each client j, let aj initialized to 1 denote the current “active” copy of j, and let Nj , initialized to Fj , be the current set of unclustered facilities in Fj ordered by increasing cij value. We will maintain the invariant facwt(Nj , j) ≥back( j) (see Lemma 5.1) for every j. Let S ={j : back( j) ≥1}be the set of candidate cluster centers. While S =∅we repeatedly do the following. C1. For each j ∈ S, let Cj (aj ) denote the average distance from j to the first l facilities (considered in sorted order) i1,...,il in Nj that gather a net xij weight of 1 (this makes sense because facwt(Nj , j) ≥ back( j) ≥ 1) where the last facility il may be included partially, that is, to an extent x such that p 0: P( j(c)) ={i : zij(c) > 0}. Let {xˆij, yˆi , zˆij(c)}denote, respectively, {xij, yi , zij(c)}/(1 −γ ). Now imagine that we have a randomized process with the following properties. FIG. 4. Local-per-client rounding. (a) Each facility i ∈/ (L1 ∪L2) (so yi <γ) is opened independently with probability yˆi . Note that yˆi <1, since yi <γ ≤1 −γ. (b) Within each cluster M, at least one facility is opened. (c) For any client j, at most one of its copies gets to use a facility, and copy c gets to use facility i ∈ P( j(c)) with probability zˆij(c). As mentioned earlier, this reference to an imaginary randomized process is for intuitive purposes only. In particular, notice that no randomized process can satisfy properties (a) and (b) simultaneously. The rounding is performed in two steps. Local per-client rounding. We first ensure that for every client j, every facility i is allotted to exactly one preferred set; so after this step, we will have zˆij(c) equal to either 0 or xˆij for every i. Fix a client j. Motivated by the aforementioned hypothetical randomized process, we write an expression Sloc(c) for the service j cost of each copy j(c). Suppose j(c) is the center of a cluster M,so M⊆P( j(c)). Let M ={i1,...,im }with ci1 j ≤ ... ≤ cim j , and let dl = cil j . One of the facilities in M is guaranteed to be open, and we assign j(c) to the nearest such facility. In Lemma 5.1, we show that yi =xij =zij(c) for each facility i in M, so we can write Sloc j (c) =yˆi1 d1 +(1 −yˆi1)yˆi2 d2 +···+(1 −yˆi1)(1 −yˆi2) ...(1 −yˆim−1)dm . (2) To avoid clutter, we have not explicitly indicated the functional dependence of Sloc j (c) on the variables yˆi1 ,...,yˆim . If j(c) is not a cluster center, let P( j(c)) ={i1,...,im }ordered by increasing distance from j, and let dl = cil j . Let M be the backup cluster of j(c), and let M\P( j(c)) ={b1,...,bq }, again ordered by increasing cij value. Denote cbl j by cl for l =1,...,q. To keep notation simple, let zˆil denote zˆil j (c). We define Sloc j (c) =zˆi1 d1 +(1 −zˆi1)zˆi2 d2 +···+(1 −zˆi1)(1 −zˆi2) ...(1 −zˆim−1)zˆimdm +(1 −zˆi1) ...(1 −zˆim )(ˆyb1 c1 +···+(1 −yˆb1) ...(1 −yˆbq−1)cq ). (3) 51:14 C. SWAMY AND D. B. SHMOYS The rationale behind the expression is the same as earlier: We assign j(c) to the nearest open facility in P( j(c)) and if no such facility is open (in which case, some facility in M\P( j(c)) must be open), then to the nearest facility opened from cluster M. Sloc Now for each j, we round the ˆzij(c) values without increasing j (c), so that c at the end we get an unsplittable allotment of facilities in Fj to copies; that is, for every i ∈ Fj there will be exactly one copy c with zˆij(c) > 0 (and hence equal to xˆij). Observe that the expression Sloc j (c) is linear in each variable zˆij(c). (This is also true when j(c) is a cluster center and i is not part of the cluster centered at j(c).) Suppose 0 < zˆij(c) < xˆij for some copy c. There must be some other copy c such that 0 < zˆij(c ) < xˆij. So if we consider changing zˆij(c)by + and zˆij(c )by − , where is either −zˆij(c)or +zˆij(c ), then since Sloc(c) and Sloc(c ) are linear in jj zˆij(c) and zˆij(c ), respectively, we can always make one of these local moves without Sloc increasing (c). In fact, notice that the values of Sloc(c ) for copies c =c,c , cj j as well as that of Sk loc(c) for any copy k(c) where k = j, remain unchanged. Thus we decrease the number of zij(.) values that lie in the interval (0,xij). Continuing in this way we get that at the end there is exactly one copy c with zˆij(c) =xˆij >0; for every other copy c we have zˆij(c ) =0. We repeat this for every facility i ∈Fj , and for every client j, to get an unsplittable allotment for each client. Figure 4 shows a possible outcome of this process. Note that the yˆi values are not changed in this step. Global rounding. Now we round the yˆi variables to 0-1 values. Each facility i with yi <γ is opened with probability yˆi , so we can write the facility cost as T (ˆy1,yˆ2,...,yˆn) = fi yˆi , where n =|F|. The service cost of a copy j(c) i:yi <γ is given by the expression Sloc(c) at the end of the local rounding step. For a cluster j Sloc center j(c), we set Sglb(c) = (c). For a noncluster-center copy j(c) we modify the expression for Sloc(c) slightly. Let P( j(c)) consist of the facilities {i1,...,im } jj j after the previous step, ordered by increasing distance from j. Recall that P( j(c)) only contains those facilities for which ˆzij(c) >0. So for any il ∈ P( j(c))wehave zˆil j (c) =xˆil j and this is equal to yˆil for all but at most one facility. Therefore, the value of Sloc(c) depends only on the ˆ values and perhaps on one xˆil j value; we j yil would like to get an expression for the service cost of j(c) that depends only on the ˆ values. So, we modify the expression for Sloc(c) as follows: We substitute yil j xˆil j with ˆ , wherever it occurs. We use Sglb(c) to denote the new expression. More yil j precisely, let M be the backup cluster of j(c) with M\P( j(c)) ={b1,...,bq }sorted by increasing cij value, let dl denote cil j for l = 1,...,m, and cl denote cbl j for l =1,...,q. We define Sglb j (c) =yˆi1 jd1 +(1 −yˆi1)ˆyi2 d2 +···+(1 −yˆi1)(1 −yˆi2) ...(1 −yˆim−1)ˆyimdm +(1 −yˆi1) ...(1 −yˆim ) yˆb1 c1 +···+(1 −yˆb1) ...(1 −yˆbq−1)cq . (4) We show in Lemma 5.7 that this modification does not increase the cost, that is, Sglb(c) ≤Sloc jj (c). The total cost is therefore given by Sglb cost(yˆ1,...,yˆn) =T (yˆ1,...,yˆn) + j (c). j,c We now convert the ˆyi values to {0,1}-values without increasing cost(ˆy1,...,yˆn). Observe that for a {0,1}-setting of the yˆi values, T (yˆ1,...,yˆn) is precisely the facility cost of the solution. Moreover, as long as the {0,1}-setting is such that each cluster contains an open facility, for each client j and for each copy c, Sglb(c)is j Sglb clearly an upper bound on the service cost of copy j(c). Hence j (c)isan c upper bound on the service cost of j. Therefore, cost(.) gives an upper bound on the total cost of the solution, satisfying property P2 of pipage rounding (Section 3.1). For any two indices i 0, we have ci k ≤ αk by complementary slackness. We will show that maxi ∈Mci j ≤ Cj (aj )/γ. This shows that cik ≤cij +ci j +ci k ≤αk +2Cj (aj )/γ ≤αk +2Ck (c)/γ, where the last inequality follows since we chose j as the current cluster center and not k. Let A⊆Nj be the set of facilities, considered in sorted order, that gather a net xij-weight of 1 (the last facility may be partially included). Here, Cj (aj ) is the average distance to the facilities in A, and M⊆A consists of the first m facilities (in sorted order) that gather an xij-weight of at least 1 − γ.Soif f is the last facility in M with cfj = maxi ∈Mci j , and B = (A\M) ∪{f }, then Cj (aj ) ≥ ( i ∈Bxi j )(mini ∈Bci j ) ≥γ ·cfj. ¯ Define Cj = cijxij. This is the cost that the LP pays to connect the rj i∈Fj copies of j. LEMMA 5.4. For any j, wehave rj 1 Cj (c) ≤C¯ j. c= PROOF. Consider the ordered (by increasing cij) set of facilities Fj . For any c,1 ≤c ≤rj , let A ⊆ Fj be the set of facilities taken in order having an xij-weight of exactly c (the last facility may be chosen partially). Define C˜ j (c) as the average distance to the set of facilities in A having a facility weight of exactly 1, picked by starting from the last facility in A. Clearly, C˜ j (c) =max{average distance toS: S ⊆ ˜¯ A,facwt(S, j) = 1}and Cj (c) = Cj . Consider any iteration when aj = c.At c this point, facwt(Nj ∩ A, j) ≥ 1, since prior to this point whenever we remove some facility weight (of at most 1) from Nj ∩ A in an iteration, we also increment aj by 1, so in all we could have removed a facility weight of at most c −1 from A. Here, Cj (c) is the average distance to the set of facilities in Nj (starting from the one closest to j) that has xij-weight 1, so Cj (c) ≤ C˜ j (c), which completes the proof. LEMMA 5.5. Let d1 ≤···≤dm+1 and 0 ≤ pl ≤1 for l =1,...,m. Consider the expression E( p1,...,pm ) = p1d1 +(1 − p1) p2d2 +···+(1 − p1) ...(1 − pm−1) pmdm +(1 − p1) ...(1 − pm )dm+1. The following properties hold. (i)E(.) ≤(1 − p)( pldl )/( pl ) + p ·dm+1, where p = (1 −pl ). l≤ml≤ml≤m (ii)E(.) is nonincreasing in each variable pi. (iii) Consider any two indices i 0}, and we add the corresponding inequalities weighted by yi , we get that jrαj − i zi ≤γfF∗+γcC∗ . Here F∗ and C∗ denote, respectively, the facility and connection cost of a fractional LP solution. (We need to be a little careful here, since we may have 0 < xij < yi for some i, j. But we can decompose the star consisting of facility i and clients {j : xij > 0}into a collection of stars {T =(i,DT )}, and weigh the inequality corresponding to star T by yT in such a way that T yT =yi and for each client j, yT = T : j∈DT xij.) Consider a star consisting of facility i and a set of k clients S ={j1,..., jk }.It suffices to bound the ratio of j∈S(αj −θij) and ( fi + j∈S cij). Let f = fi ,dj =cij, (c)(r) and vj =αj −θij. Note that vj =αj if j(c) is primarily connected to f , and αj otherwise. We number the demands 1 ...k so that v1 ≤... ≤vk . Consider the time t =vi − . At this time each demand j k facilities, and a single dual solution. The two primal solutions can be found in polynomial time by performing a bisection search in the interval [0, nr maxij cij] and terminating the search when the length of search interval becomes less than 2(− poly(n)+ L), where L = log(maxij cij). The proof is very similar to that in the conference version of Jain and Vazirani [2001]. Let (α, β, z, 0) be the common dual solution for the two primal solutions. The dual solution (α, β, z, 0) is used only in the analysis and not in the algorithm. Let (x1, y1) and (x2, y2) be the two solutions opening k1 < k and k2 > k facilities with costs (F1, C1) and (F2, C2), respectively. A convex combination of these two yields a fractional solution that is feasible in (KP) and opens exactly k facilities. Let a, b be such that ak1 +bk2 =k, a +b =1. Then, 2(aF1 +bF2) +(aC1 +bC2) ≤2 αj − zi −k ≤2 ·OPTk . (10) ji We will round this solution, losing a factor of 2. If a ≥ 12, we take the solution (x1, y1), which is feasible and from Eq. (10) and get that F1 +C1 ≤ 4 ·OPTk . Otherwise, we open a subset of the facilities opened in y2. We call a facility opened in y1a “small” facility and opened in y2a “large” facility; a facility opened in both is both small and large. We match each small facility with a large facility as follows: A small facility that is also large is matched with itself. We consider the other small facilities in arbitrary order, and pair each small facility with the unpaired large facility closest to it. Note that exactly k1 large facilities are matched this way. With probability a, we open all the small facilities, and with probability b =1 −a we open all the matched large facilities. We also select a random subset of k −k1 unmatched large facilities and open all of these. Each client j is simply connected to the rj =r open facilities closest to it. Each large facility is opened with probability b = k−k1 , therefore the total facility opening cost is at most aF1 +bF2. k2 −k1 LEMMA 7.1. The total facility opening cost incurred in at most aF1 +bF2. LEMMA 7.2. The expected connection cost of a demand j is at most 2 i cij (ax1,ij +bx2,ij). PROOF. We will prove the claimed bound by considering a suboptimal way of assigning j to r open facilities (instead of connecting j to the r nearest open facilities), and bounding the connection cost of j under this suboptimal assignment. Let Sj be the set of small facilities to which j is connected, namely, Sj ={i : x1,ij = 1}. Similarly, let Lj be the set of large facilities that serve j. Clearly |Sj |=|Lj |=r. For each copy j(c) we define a set of facilities Tc, and j(c) will only be connected to a facility in Tc. First, we arbitrarily assign each facility i ∈Sj , and the large facility i to which it is matched (which could be the same as i), to a distinct set Tc. Observe the important fact that the sets Tc are disjoint, since distinct facilities in Sj are matched to distinct large facilities. Let m(Sj ) denote the set of large facilities that are matched to facilities in Sj . Then |m(Sj )|=|Sj |=|Lj |=⇒|m(Sj )\Lj |=|Lj \m(Sj )|,so the number of sets Tc not containing a facility from Lj after the first step is equal to the number of unmatched facilities in Lj . We assign a distinct unmatched facility of Lj to each set Tc which does not already contain a facility from Lj . Note that the sets Tc remain disjoint; so if we connect each copy j(c) to a facility in Tc,we will get a feasible solution. For convenience, if facility i ∈Sj is matched with i , we will consider i and i as two different facilities even if i =i . Let X be the service cost of j and X(c) be the service cost of j(c). Fix copy c. The set Tc contains at least one small facility i1 ∈Sj and one large facility i2 such that i1 is matched to i2. If these are the only two facilities then it must be that i2 ∈Lj . Exactly one of i1 and i2 is open; we assign j(c) to i1 or i2, whichever is open. So E[X(c)] =aci1 j +bci2 j . Otherwise, Tc contains a third facility i3 ∈Lj such that i3 is unmatched and i2 ∈/ Lj . We assign j(c) to i3 if it is open, otherwise to i1 or i2, whichever is open. So E[X(c)] =bci3 j +a(aci1 j +bci2 j ). 51:26 C. SWAMY AND D. B. SHMOYS Since i1 is matched with i2 and i3 is unmatched, it must be that i2 is closer to i1 than to i3. So, ci2 j ≤ ci1 j + ci1i2 ≤ ci1 j + ci1i3 ≤ 2ci1 j + ci3 j . Therefore E[X(c)] ≤ bci3 j + a(aci1 j + 2bci1 j + bci3 j ) = a(1 + b)ci1 j + b(1 + a)ci3 j ≤ 2(aci1 j + bci3 j ). Thus for every copy c,if i, i ∈ Tc, where i ∈ Sj and i ∈ Lj , we have that E[X(c)] ≤ 2(acij + bci j ) = 2(acijx1,ij + bci jx2,ij ), since x1,ij = x2,ij = 1. So, summing over all copies c, since the set of all facilities i is precisely Sj and the set of all facilities i is the set Lj ,weget E[X] ≤ 2( acijx1,ij + bcijx2,ij ) = i∈Sj i∈Lj 2 i cij(ax1,ij +bx2,ij ), where the last equality follows since if i ∈/ Sj , then x1,ij = 0, and if i ∈/ Lj , then x2,ij = 0. THEOREM 7.3. The aforesaid algorithm returns a solution of expected cost at most four times the optimum for the fault-tolerant k-median problem with uniform requirements. PROOF. By Lemma 7.2, the expected service cost of client j is at most 2 i cij(ax1,ij + bx2,ij). Also we have C1 = j,i cijx1,ij and C2 = j,i cijx2,ij . So summing over all j, we see that the expected total service cost is at most 2(aC1 +bC2). Combining this observation with Lemma 7.1, the expected total cost of the solution returned is at most (aF1 + bF2) + 2(aC1 + bC2) ≤ 4 · OPTk , from Eq. (10). ACKNOWLEDGMENTS. We thank the anonymous referees for their useful suggestions. REFERENCES AGEEV, A., AND SVIRIDENKO, M. 2004. Pipage rounding: A new method of constructing algorithms with proven performance guarantee. J. Combinatorial Optim. 8, 307–328. ARYA, V., GARG, N., KHANDEKAR, R., MEYERSON, A., MUNAGALA, K., AND PANDIT, V. 2004. Local search heuristics for k-median and facility location problems. SIAM J. Comput. 33, 544–562. CHARIKAR,M., AND GUHA, S. 2005. Improved combinatorial algorithms for facility location problems. SIAM J. Comput. 34, 803–824. CHARIKAR, M., GUHA, S., TARDOS, E., AND SHMOYS, D. B. 2002. A constant-factor approximation ´ algorithm for the k-median problem. J. Comput. Syst. Sci. 65, 129–149. CHUDAK,F., AND SHMOYS, D. 2003. Improved approximation algorithms for the uncapacitated facility location problem. SIAM J. Comput. 33, 1–25. GUHA, S., AND KHULLER, S. 1999. Greedy strikes back: Improved facility location algorithms. J. Algor. 31, 228–248. GUHA, S., MEYERSON, A., AND MUNAGALA, K. 2003. Improved algorithms for fault tolerant facility location. J. Algor. 48, 429–440. HARDY, G. H., LITTLEWOOD,J.E., AND POLYA, G. 1952. Inequalities. Cambridge University Press, UK. ´ JAIN, K., MAHDIAN, M., MARKAKIS, E., SABERI, A., AND VAZIRANI, V. 2003. Greedy facility location algorithms analyzed using dual-fitting with factor-revealing LP. J. ACM 50, 795–824. JAIN, K., MAHDIAN,M., AND SABERI, A. 2002. A new greedy approach for facility location problems. In Proceedings of the 34th Annual ACM Symposium on Theory of Computing (STOC), 731–740. JAIN, K., AND VAZIRANI, V. V. 2000. An approximation algorithm for the fault tolerant mertic facility location problem. In Proceedings of 4th International Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX). 177–183. JAIN, K., AND VAZIRANI, V. V. 2001. Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and Lagrangian relaxation. J. ACM 48, 274–296. KORUPOLU,M.R., PLAXTON,C.G., AND RAJARAMAN, R. 2000. Analysis of a local search heuristic for facility location problems. J. Algor. 37, 146–188. LIN,J.H., AND VITTER, J. S. 1992. -approximations with minimum packing constraint violation. In Proceedings of the 24th Annual ACM Symposium on Theory of Computing (STOC), 771–782. MAHDIAN, M., MARKAKIS, E., SABERI, A., AND VAZIRANI, V. 2001. A greedy facility location algorithm analyzed using dual-fitting. In Proceedings of 4th International Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX). 127–137. MAHDIAN, M., YE,Y., AND ZHANG, J. 2006. Approximation algorithms for metric facility location problems. SIAM J. Comput. 36, 411–432. METTU,R.R., AND PLAXTON, C. G. 2003. The online median problem. SIAM J. Comput. 32, 816–832. MIRCHANDANI,P., AND FRANCIS, R. 1990. Discrete Location Theory. John Wiley, New York. SHMOYS,D.B., TARDOS, E., AND AARDAL, K. I. 1997. Approximation algorithms for facility location ´ problems. In Proceedings of the 29th Annual ACM Symposium on Theory of Computing (STOC), 265–274. SVIRIDENKO, M. 2002. An improved approximation algorithm for the metric uncapacitated facility location problem. In Proceedings of the 9th Conference on Integer Programming and Combinatorial Optimization (IPCO), 240–257. SWAMY,C., AND SHMOYS, D. B. 2003. Fault-Tolerant facility location. In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 735–736. VAZIRANI, V. 2001. Approximation Algorithms. Springer, NY. RECEIVED AUGUST 2005; REVISED SEPTEMBER 2007; ACCEPTED OCTOBER 2007