Approximating the Two-Level Facility Location Problem Via a Quasi-Greedy Approach
Jiawei Zhang
Abstract We propose a quasi-greedy algorithm for approximating the classical uncapacitated 2-level facility location problem (2-LFLP). Our algorithm, unlike the standard greedy algorithm, selects a sub-optimal candidate at each step. It also relates the minimization 2-LFLP problem, in an interesting way, to the maximization version of the single level facility location problem. Another feature of our algorithm is that it combines the technique of randomized rounding with that of dual fitting. This new approach enables us to approximate the metric 2-LFLP in polynomial time with a ratio of 1.77, a significant improvement on the previously known approximation ratios. Moreover, our approach results in a local improvement procedure for the 2-LFLP, which is useful in improving the approximation guarantees for several other multi-level facility location problems. 1 Intro duction 1.1 Problem statement In the single level uncapacitated facility location problem, we are given a set of clients and a set of facilities. We want to open a subset of the facilities such that all the clients are served by the open facilities, and that the total cost of opening facilities and serving clients is minimized. In the k -level uncapacitated facility location problem (k -LFLP), the demands must be routed among the facilities in a hierarchical order, i.e., from the highest level (the factories) to the lowest (the retailers), before reaching the clients. The k -LFLP arises naturally in designing logistic systems. The k -LFLP can be formulated formally as follows. We are given a set of clients D and k level sets of facilities F1 , F2 , · · · , Fk . Denote P = F1 × F2 × · · · × Fk and F = k=1 Ft . Each client j  D must be served by t an open path p = (i1 , i2 , · · · , ik )  P of k facilities with exactly one from each of the k levels, where a path p is open if and only if every facility on the path is open. There is a facility cost fit for opening facility it  Ft (1  t  k ). Furthermore, If client j  D is served by an


open path p = (i1 , i2 , · · · , ik )  P a connection cost cj p k is incurred where cj p = cj i1 + t=2 cit-1 it and cj i is the connection cost between j and i for j, i  D  F . Here, we wish to open a subset of facilities such that each client is assigned to an open path and the total cost is minimized, i.e., to choose  = St  Ft , t = 1, 2, · · · , k , such that j
D

pS1 ×S2 ×···×Sk

min

cj p +

tk i
=1
t  St

fit

is minimized. We also assume that the connection costs are nonnegative, symmetric, and satisfy the triangle inequality, i.e., for each i, j, l  D  F , cij  0, cij = cj i and cij  cil + clj . In this paper we are concerned with the 2-LFLP, the most studied special case of k -LFLP in the literature of Operations Research for k  2 [1, 8, 16, 17, 19, 27, 28, 29, 32]. The study on the 2-LFLP is motivated by the fact that in many applications, especially in supply chains, there are hierarchical two-level structures. The problem also has applications in telecommunications and computer network designs [8]. On the other hand, although it is the simplest model among all the k -LFLP for k  2, the 2-LFLP has some fundamental structural differences from the 1-LFLP. For example, the 2-LFLP does not possess the so-called supermodularity, a wellknown property for the 1-LFLP [20]. This property is often helpful in designing branch-and-cut algorithms and in analyzing some approximation algorithms. Thus, the 2-LFLP needs new techniques.

1.2 Previous results The 2-LFLP generalizes the popular single level uncapacitated facility location problem (1-LFLP), which is already NP-hard [13]. Since the work of Shmoys, Tardos and Aardal [31], designing approximation algorithms for the 1-LFLP and its related problems has received considerable attention during the past few years [30]. We call an algorithm of a minimization problem a ( 1)-approximation algorithm if for any instance of the problem the algorithm runs in polynomial time and outputs a solution that has a cost  Department of Management Science and Engineering, Stanford University, Stanford, CA, 94305, USA. Email: at most  times the minimal cost, where  is called the performance guarantee or the approximation ratio jiazhang@stanford.edu.
Copyright © 2004 by the Association for Computing Machinery, Inc. and the Society for industrial and Applied Mathematics. All Rights reserved. Printed in The United States of America. No part of this book may be reproduced, stored, or transmitted in any manner without the written permission of the publisher. For information, write to the Association for Computing Machinery, 1515 Broadway, New York, NY 10036 and the Society for Industrial and Applied Mathematics, 3600 University City Science Center, Philadelphia, PA 19104-2688

808


of the algorithm. Guha and Khuller [18] proved that the existence of a polynomial time 1.463-approximation algorithm for the 1-LFLP would imply that P = N P . And the best currently known approximation ratio for the 1-LFLP is 1.52 due to Mahdian, Ye and Zhang [24]. Therefore, the approximability of the 1-LFLP is well understood. However, the 2-LFLP remains intriguing. One can easily see that the lower bound 1.463 of the 1-LFLP also applies to the 2-LFLP, and no better lower bound is known. In [31], the algorithm for the 1-LFLP has been extended to the 2-LFLP with an approximation ratio 3.16. Later on, Aardal, Chudak and Shmoys [2] showed that the k -LFLP can be approximated in polynomial time by a factor of 3 for any k  2 using a linear programming relaxation. However, their algorithm does not possess a better performance guarantee for k = 2, neither do a series of recently proposed faster combinatorial algorithms due to Meyerson, Munagala, and Plotkin [26], Guha, Meyerson, and Munagala [22], Bumb and Kern [7], and Ageev [3]. In fact, the algorithms of [2, 7, 3] will produce solutions whose open paths are disjoint, and Edwards [15] showed that such algorithms can not have worst case ratios that are better than 3 even for k = 2. Very recently, Ageev, Ye, and Zhang [5] proposed two different combinatorial algorithms and showed that `the better of the two' has a performance guarantee 2.43, although each of them has a performance guarantee at least 3. 1.3 New results and techniques The main result of this paper is that the 2-LFLP can be approximated in polynomial time by a factor of 1.77, a significant improvement over the previous performance guarantees, since no one can do better than 1.463 unless P = N P . The improved ratio is achieved by using what we call a quasi-greedy approach. Our algorithm is analyzed by using the technique of factor-revealing LP developed by Jain, Mahdian, and Saberi [23]. One advantage of our algorithm is that it can be easily generalized to solve the so-called two level concentrator location problem (see [9] and the references therein) with the same ratio 1.77. The quasi-greedy approach also results in a local improvement procedure for the 2-LFLP, which does not improve the ratio 1.77 for the 2-LFLP but is useful in improving the performance guarantees for other multilevel facility location problems. In particular, we show that 3- and 4-LFLP can be approximated by factors of 2.51 and 2.81, respectively, obtaining the current best approximation ratios for these two problems. We also obtain an improved 3-approximation algorithm for the 2-LFLP with soft capacities. Greedy algorithms have been successful in tackling

the 1-LFLP [23, 24]. In a standard greedy approach, at each step, one computes a greedy function value for each element of a candidate set and chooses the optimal candidate based on these values. When applied to the 1-LFLP, the candidate set is the set of (unopen) facilities, and the greedy function is the ratio of the cost incurred to the number of new clients served, which can be computed easily. However, the issue is more complicated when we apply the greedy approach to the 2-LFLP. In particular, it is difficult to define a candidate set. Some straightforward choices do not work such as F1  F2 and F1 × F2 . One sophisticated definition works where a candidate is defined as many facilities with exactly one in F2 and the rest in F1 . Unfortunately, the problem is that there are exponentially many candidates, and we can not choose the best candidate by comparing their greedy function values with each other in polynomial time. Thus, we make a simple but important observation for the 2-LFLP: choosing the best candidate among the exponentially many candidates according to an `easy' greedy function is equivalent to choosing the best candidate among polynomially many candidates according to an appropriately defined `hard' greedy function. In the latter, given a candidate, it is NPhard to compute the exact value for the `hard' greedy function. But the good news is that we may compute the greedy function value approximately in polynomial time. Therefore, we could choose the `best' candidate according to the approximated greedy function value. We call this approach quasi-greedy since it may not choose the `greediest' candidate. It turns out that computing the `hard' greedy function value for solving the 2-LFLP is equivalent to the so-called maximization version of the 1-LFLP (Max1-LFLP in short). Recall that in the minimization 1LFLP, assigning a client to an open facility will incur a connection cost. In the Max-1-LFLP, a revenue will be generated by assigning a client to an open facility, and the ob jective is to maximize the net profit (the total revenue minus the total facility cost). The Max1-LFLP and the minimization 1-LFLP are equivalent from the perspective of optimization, but not from that of approximation. Approximation algorithms for the Max-1-LFLP have a longer history than those for the 1-LFLP[12, 4]. However, the results of [12, 4] do not help in establishing our result for the 2-LFLP. We shall give a new approximation algorithm for the Max-1LFLP such that the approximation result can be used in proving our bound for the 2-LFLP. To the best of our knowledge, this is the first time that approximations for the maximization and the minimization versions of a facility location problem have been related.

809


We remark that the quasi-greedy approach has been used in designing approximation algorithms in other settings, for example, Chekuri, Even and Kortsarz [11]. However, our approach is new in that it reduces the size of the set of candidates from exponentially many to polynomially many in such a way that the greedy function for the latter can be well approximated. Our algorithm and analysis combine the technique of randomized rounding with that of dual fitting. Both of the two techniques have been used for solving various facility location problems, but never combined before . In our algorithm, each greedy step is solved by randomly rounding the solution of its linear programming relaxation. Dual fitting (and the factor-revealing LP) is used for proving the overall performance guarantee. 1.4 Organization of the pap er The rest of the paper is organized as follows. In Section 2, we present a linear programming based approximation algorithm for the Max-1-LFLP. The quasi-greedy algorithm for the 2LFLP and its analysis is given in Section 3. In Section 4, a local improvement procedure based on the quasigreedy approach for the 2-LFLP is proposed. In section 5, we present improved approximation algorithms for the two level concentrator location problem and other multi-level facility location problems. Final remarks are given in Section 6.

the total revenue and the total facility cost, respectively. Our goal is to find an algorithm that produces a solution with profit C - F  (1 - 1 )C  - F  . The algorithm e is based on the linear programming (LP) relaxation of this problem. However, the actual LP we will solve is different from the exact LP relaxation of (2.1). Algorithm MAX Step 1. Solve the following LP and obtain an optimal solution (x, y ): i 1i (2.2)Max dij xij - fi yi (1 - ) · e F ,j D F i xij = 1 for all j  D s.t.
F

xij  yi for all i  F , j  D 0  xij , yi  1 for all i  F , j  D Step 2. For each i  F , open facility i independently with probability yi , and assign each client j  D to an open facility with maximum revenue. Let the resulted solution be (x, y ) and the corresponding facility ^^ cost and revenue be F and C respectively. We first prove a technical lemma. Lemma 2.1. Given 3n reals di , ti and pi , i = 1, 2, · · · , n such that d1  d2  · · ·  dn  0, 0  ti  pi  1 and n i=1 ti = 1, then 1 n k -1 kn i in i dk (1 - pi )pk  - (1 - ti ) di ti .

2 An algorithm for the Max-1-LFLP =1 =1 =1 =1 In this section, we consider the maximization version of the (single level) facility location problem (Max-1- Proof. Let LFLP). In the Max-1-LFLP, we are given the set of k -1 kn i client D, the set of facilities F . The facility cost for g (z1 , z2 , · · · , zn ) = dk (1 - zi )zk . opening facility i is fi and , The revenue generated by =1 =1 assigning client j to facility i is dij  0 . Here dij may not satisfy the triangle inequality. The ob jective is One can verify that to open a subset of the facilities of F and then assign g each of the clients in D to an open facility such that  zk   the net profit is maximized. The Max-1-LFLP can be k-1 l j -1 i jn formulated as the following integer program. = (1 - zi ) · dk - dj z j (1 - zl ) i i =1 =k+1 =k+1 (2.1) Max dij xij - fi yi   s.t. i
F ,j D F

xij = 1 for all j  D for all i  F, j  D



k-1 i =1

(1 - zi )dk · 1 - j
n

j

n

zj
=k+1

l j -1

(1 - zl )

F

=k+1

xij  yi

xij , yi  {0, 1} for all i  F , j  D where yi = 1 if we decide to open facility i, otherwise yi = 0; xij = 1 if client j is assigned to facility i, otherwise xij = 0. Consider any feasible solution, whose total profit is assumed to be C  - F  , where C  and F  correspond to

=

k-1 i =1

(1 - zi )dk ·

(1 - zj )
=k+1

0 Therefore, g (z1 , z2 , · · · , zn ) is nondecreasing function of zi for each i = 1, 2, · · · , n. It follows that g (p1 , p2 , · · · , pn )  g (t1 , t2 , · · · , tn ).

810


Let D = d1 + 1. And let ci = D - di for i = 1, 2, · · · , n. the subscript j and denote the revenues by d1 , d2 , · · · , Therefore, 0 nc1  c2  · · ·  cn . Furthermore, by such that di  di+1 . By conditional probability, assumption, i=1 ti = 1, then by Lemma 10 of Chudak k-1 y i 1 i and Shmoys [14], we must have E[ di xij ] = ^ dk (1 - yi ) k . 1 ·n k-1 n n =1 F k|F | i i i k (1 - ti ) ci ti . ck (1 - ti )tk  - k Furthermore, 0  xkj  yk and =1 =1 =1 =1 F xkj = 1 for every j. Therefore, by Lemma 2.1, the expected revenue that It implies that j can get is bounded below by 1 i k-1 kn i i 1i (D - dk ) (1 - ti )tk di xij . - (1 - xij ) di xij  (1 - ) e =1 =1 F F F 1 ·n in i  - (1 - ti ) (D - di )ti . The last inequality holds since =1 =1 i i 1 |F | 1 F xij |F | )  (1 - ) . (1 - xij )  (1 - Rearrange the above inequality, we get |F | |F | e F 1 ·n k-1 kn i in i Therefore, dk (1 - ti )tk  - (1 - ti ) di ti .
=1 =1 =1 =1

Therefore, g (p1 , p2 , · · · , pn )  g (t1 , t2 , · · · , tn ) 1 in  - (1 - ti )
=1

i E[
F ,j D

i dij xij ] - E[ ^
F

fi yi ] ^ i
calF

 · in
=1

1i (1 - ) e

dij xij -
F ,j D

fi yi .

di ti ,

which completes the proof. Now we are ready to present the main result of this section. Theorem 2.1. There exists an algorithm that finds a solution with profit C - F such that 1 C - F  (1 - )C  - F  . e Proof. By the definition of (x, y ), yi is 1 with probability ^^ ^ yi , and 0 with probability 1 - yi . Then E[yi ] = yi and ^ thus the expected facility cost is i i i E[F ] = E[ fi yi ] = ^ fi E[yi ] = ^ fi y i .
F F F

Since (x, y ) is the optimal solution for the LP, the right hand side of the above inequality is bounded below by (1 - 1 )C  - F  . Therefore, e 1 E[C - F ]  (1 - )C  - F  . e By the standard technique using conditional expectation, we can derandomize the algorithm such that 1 C - F  (1 - )C  - F  . e 3 The quasi-greedy algorithm for the 2-LFLP For our purpose, it would be useful to have the following definition. Definition 3.1. An algorithm is cal led a (Rf , Rc )approximation algorithm for the k -LFLP, if for every instance I of the k -LFLP, and for every solution S OL for I with facility cost F S OL and connection cost C S OL , the cost of the solution found by the algorithm is at most Rf F S OL + Rc C S OL . We cite a lemma from Mahdian et al [24]. Lemma 3.1. [24] For (a, b) = (1.104, 1.78) or (a, b) = k k (1.118, 1.77), i=1 i  a · i=1 mi + b · f , if the

It is left to analyze the quantity i E[C ] = E[ dij xij ]. ^
F ,j D

Consider any j  D, and assume that the facilities are indexed such that dij  d(i+1)j . For simplicity, we drop

811


Bj is used to denote the amount of money available to Bj to offer. Before j is connected, Bj = j . The first  1  j < k : j  j +1 time j is connected to an open path, say p, Bj = cj p . It  1  l < j < k : rl,j  rl,j +1 is clear that Bj  cj p . After j is connected, Bj is the  1  l < j  k : j  rl,j + mj + ml connection cost paid by client j . For example, client j j -1 (3.3) 1  j  k : may get connected later to another open path p with l=1 max(rl,j - ml , 0) k + l=j max(j - ml , 0)  f cj p  cj p to save the connection cost. Then as long as  1  l  j  k : j , mj , f , rl,j  0. j is connected to p , Bj = cj p . Therefore, the value Bj will not stop increasing until j gets connected to an Furthermore, the 1-LFLP can be approximated by a open path (it may start decreasing from then on). factor of (a + ln( ), 1 + (b - 1)/ ) for any   1. Remark 2. In order to implement Algorithm QG in Below are the details of our quasi-greedy algorithm polynomial time, we notice that the total number of for the 2-LFLP. The algorithm is presented in a way possible events is bounded by |D| + |F2 |. At any time, we need to find the minimum value of how much the similar to that of Jain et al [23]. j 's should increase such that the next event will occur. Algorithm QG 1. We introduce a notion of time. The algorithm This can be done in polynomial time (but not strongly starts at time 0. At this time, all clients are unconnected polynomial time) by performing a bisection search. and all facilities are unopen. Let U be the set of Another way for implementing the algorithm is that we unconnected clients. Thus at this time U = D. And discretize the time and only consider the values of j 's that are powers of (1 + ), i.e., {0, 1, (1 + ), (1 + )2 , (1 + j = 0 for each j  D. 3 At each moment, every client j will have some ) , · · · , } for any given constant > 0. Therefore, the money Bj available to offer to each unopen facility in algorithm can be implemented in polynomial time for F2 , where Bj = j if j is unconnected, and Bj = cj p if any given constant > 0. Now, we are ready to analyze the algorithm. First, j is currently connected to an open path p. The amount we have of offers received by a facility i  F2 is computed as follows. Consider any i  F2 . For each j  D Lemma 3.2. The total cost of the solution produced by and k  F1 , define dkj = max{Bj - cj ki , 0} where Algorithm QG is j  . D j ^ cj ki = cj k + cki , and fk = 0 if k  F1 is already open; ^ We can assume that the open paths of an optimal fk = fk otherwise. Then we obtain an instance of the Max-1-LFLP. We solve this instance by Algorithm MAX solution of the 2-LFLP form a forest [15]. In order to and obtain a feasible solution. This profit (could be analyze the performance guarantee, we consider any tree negative) is the amount of offers received by the facility of the forest. The root of this tree must be a facility i. Note that each client j can make an offer to a facility i  F2 . And the leaves of the tree are a subset of i  F2 through exactly one facility i (j )  F1 where the facilities, say Si  F1 . We also consider the set i (j ) is the facility to which j is assigned by Algorithm of clients, denoted by Di , who are assigned to the tree MAX. The contribution made by client j to facility i is rooted at i in the optimal solution. Therefore, the total cost (of the optimal solution) associated with this tree equal to di (j )j . 2. While U = , increase the time and simultane- is k j fi + fk + min cj ki . ously increase j at the same rate for each j  U , until k  Si Di  Si one of the following events occurs: (1). For a unopen facility i  F2 , the total amount If we could prove that, for each i  F2 , of offers that it has received from the clients is equal to f + j k j fi . In this case, we open facility i. And for each client j  Rf · fk Rc · min cj ki , i+ k  Si j  D who has made non-zero contribution to i, we open Di Di Si facility i (j )  F1 and assign j to the path (i (j ), i). Furthermore, if j  U , then remove j from U (and stop then Algorithm QG must be a (Rf , Rc )-approximation increasing j ). algorithm for the 2-LFLP. Thus, in the rest of this (2). For a client j  U and open facilities i  F2 section, we consider a particular i, and the associated and k  F1 , j = cj ki , then assign j to the path (k , i) Si and Di . We assume that |Di | = n and let mj = and remove j from U (and stop increasing j ). minkSi cj ki . Furthermore, without losing generality, we Remark 1. For each client j  D, the value j will assume that 1  2  · · ·  n . increase until j gets connected to an open path, and j For each j : 1  j  n, consider the situation of will not change after that. At each moment, the value the algorithm at time t = j . For each l  j - 1, if l is

following system of inequalities holds

812


connected to a path p before time t (i.e. l was connected to a path at time j /(1 + ) , then let rl,j = clp ; otherwise, let rl,j = l . In the latter case, l = j . f , k e Lemma 3.3. Let f = e-1 i + then the  Si f k system of inequalities (3.4) holds:  1  j < k : j  j +1  1  l < j < k : rl,j  rl,j +1  1  l < j  k : j /(1 + )  rl,j + mj + ml j -1 (3.4) 1  j  k : l=1 max(rl,j /(1 + ) - ml , 0) k + l=j max(j /(1 + ) - ml , 0)  f  1  l  j  k : j , mj , f , rl,j  0. Proof. First of all, the inequality j  j +1 holds by assumption. And for each l : 1  l < j  n, we have rl,j  rl,j +1 since once a client is connected to a path, it will never be connected to a path with a higher connection cost. Consider clients j > l at time t = j . If l is unconnected at time t/(1 + ), then by definition, rl,j = l and it must be the case j = l . Therefore, j  rl,j + mj + ml . Now we assume that l is connected to a path p at time t/(1+ ). It follows that rl,j = clp and p must be open at time t/(1 + ). Thus t/(1 + )  cj p , otherwise j could be connected to p before time t. However, by triangle inequality, cj p  clp + mj + ml . Thus, we also have j /(1+ ) = t/(1+ )  rl,j +mj +ml . It is left to prove that for all j ,
j -1 l =1

the Max-1-LFLP with total profit at least 1l (1 - ) e max{Bl - ml , 0} -
Di

k
 Si

fk .

However, the total amount of offers received by i from the clients is at least this quantity that can not be greater than the fi . Therefore, 1l (1 - ) e max{Bl - ml , 0} -
Di

k
Si

fk  fi .

Rearranging the terms in the above inequality, we get the desired conclusion. Theorem 3.1. The 2-LFLP can be approximated by a factor of 1.77(1 + )2 in polynomial time for any given constant > 0. Proof. By Lemma 3.1 and Lemma 3.3, by comparing systems (3.3) and (3.4), and by using the pair (a, b) = (1.118, 1.77), we get j j
Di

(1 + )2 f
i

e  1.118 · e-1

+

k
Si

+ fk 1.77 ·

j
Di

mi ,

max (rl,j /(1 + ) - ml , 0) max (j /(1 + ) - ml , 0) f
i

which, together with Lemma 3.2, implies that Algorithm QG is a 1.77(1 + )2 -approximation algorithm for e the 2-LFLP since 1.118 · e-1  1.77. We mention that the above analysis would lead to an O(ln(|D|))-approximation algorithm for the non-metric 2-LFLP where the connection cost may not satisfy the triangle inequality. 4

+

ln
=j

A lo cal improvement pro cedure for the 2-LFLP The main result of this section is that given a (Rf , Rc )At time t = j /(1 + ), Algorithm QG will construct an instance of the Max-1-LFLP, i.e., for each client l  D approximation algorithm for the 2-LFLP, we can find an tm and facility k  F1 , define dkl = max{Bl - clki , 0}. Note approximation algoriRh-1 with performance guarantee e (Rf + e-1 ln( ), 1 + c ) for any   1 in polynomial that Bl  rl,j /(1+ ) for l < j and Bl = t for l  j . Then we consider a feasible solution of the Max-1-LFk P. We time. We will see its application in the analysis of L algorithms for the 3-LFLP and the 4-LFLP, among open facilities in Si with opening cost at most  Si f k . For each l  Di , we assign l to the facility in Si , to which others. A similar result has been proved for UFLP l is connected in the optimal solution of the 2-LFLP. by Guha and Khuller [18] and we have seen many For other clients not in Di , we assign them to any open applications of it [10, 18, 24, 25, 5]. The key here is again the quasi-greedy approach. In facility. The total profit of this solution is at least order to prove the above result, we design a local imk l provement procedure for the 2-LFLP. Roughly speakmax{Bl - ml , 0} - fk . ing, once we have a feasible solution for the 2-LFLP, Di  Si we may add some facilities to the current solution such By Theorem 2.1, Algorithm QG can find a solution for that the total cost is reduced.
 Si



e e-1

+

k

. fk

813


The local improvement procedure proceeds as follows, which is similar to Algorithm QG. We are given a solution for the 2-LFLP. Assume the connection cost of each client j  D is oj . We want to add some facilities (open one facility in F2 and simultaneously many facilities in F1 ) into the current solution. At each step, we consider an unopen facility i  F2 . We construct an instance of the Max-1-LFLP: we are given the set of clients D, the set of facilities F1 , the facility cost for opening k  F1 is fk (we can let fk = 0 if k has been open in the current solution), and the revenue generated by assigning j  D to k  F1 is dj k = max{0, oj - cj ki }. Again, we solve the Max-1-LFLP by using Algorithm MAX. Assume that client j is assigned to i (j ) by Algorithm MAX. If the total profit of the solution for the Max-1-LFLP is greater than fi , then the total cost of the current solution for the 2-LFLP can be reduced by opening facility i, and for each client j , if dj i (j ) > 0 then open i (j ) and re-connect j to the path (i (j ), i). Such a step is called an `add operation'. Repeat this procedure until the solution can not be improved by any 'add operation' Consider any feasible solution, say OP T , for the 2LFLP. Assume its total connection cost and facility cost are C opt and F opt . Again, w.l.o.g., we can assume that the solution OP T forms a forest. Consider one of the trees rooted at i  F2 . Let Si and Di be defined as those in the last section. Now we are ready to prove the following Lemma, whose counterpart for the 1-LFLP is well-known in this area. Lemma 4.1. If no more `add operation' can improve the e current solution, then C  C opt + e-1 F opt .

However, since no `add operation' can improve the current solution, we must have 1j fi  (1 - ) e (oj - j ) -
Di

k
Si

fk .

Note that for i = l, Di  Dl = , iOP T (F2 ) Di = D i and iOP T (F2 ) F1 = OP T (F1 ). Then we add the above inequality over i  OP T (F2 ), which completes the proof. The above lemma leads to the following conclusion immediately: Lemma 4.2. If there is an (a, b)-approximation algorithm for the 2-LFLP, then we can get an approximation algorithm with performance guarantee a f e + e-1 ( - 1), 1 + b-1 or any   1.  Proof. Assume that there is an (a, b)-approximation algorithm for 2-LFLP, then by scaling the facility cost of the original instance by a factor of   1, we can find a solution such that F + C  aF OP T + bC OP T . Then we apply the local improvement procedure on this solution, until the cost (on the scaled instance) can not be reduced anymore. Then we must have, by Lemma 4.1, e C  C OP T + F O P T . e-1

Combining these two inequalities, we must have a F Proof. Let OP T (Fi ) be the subset of facilities in Fi that e b - 1 OP T OP T F +C  + ( - 1) + (1 + )C . are open in the feasible solution OP T , for i = 1, 2. In e-1  the local improvement procedure, assume that we are considering a candidate facility i  OP T (F2 ). Let the Theorem 4.1. For any given > 0, if there is an connection cost of client j be, oj in the current solution, (a, b)-approximation algorithm for the 2-LFLP, then we and j in OP T . can get an a pproximation algorithm with performance a f As in the proof of Lemma 3.3, there exists a feasible e guarantee + e-1 ln() + , 1 + b-1 or any   1.  solution for the Max-1-LFLP with total profit at least j
Di

max{oj - j , 0} -

k
 Si

fk .

Therefore, Algorithm QP can find a solution with total profit at least 1j (1 - ) e  1j (1 - ) e max{oj - j , 0} -
Di

k
 Si

fk

(oj - j ) -
Di

k
Si

fk .

Proof. Assume that we have an (a, b)-approximation algorithm for 2-LFLP. Let   1. We prove that for any integer p  1, there exists an approximatia n algorithm for 2-LFLP . ith performance guarantee o w e - + e-1 p( - 1), 1 + bp1 We prove the claim by induction on p. The case p = 1 is trivial by Lemma 4.2. Assume that the claim is correct for p - 1. Then a b- we have an + e(p-e1)(-1) , 1 + p-1 approximation 1 -1 algorithm for 2-LFLP. We apply Lemma 4.2 again, then

814


we get an approximation algorithm with performance guarantee a , b- 1 + p-1 - 1 e(p - 1)( - 1) e( - 1) 1 + + ,1 + e-1 e-1 p

which is exactly what we need. Thus we have proved the claim for any integer p. 1 Theorem 5.1. Assume that the 1- and 2-LFLP can be Now for any   1, let  =  p for some large integer approximated by factors of (a, b) and (,  ), respectively, p. We have thus proved that any (a, b)-approximation a - then the 3- and 4-LFLP can be approximated by factors 1 e + algorithm implies an + e-1 p( p - 1), 1 + b-1 of (max{a, a+ }, 3b2  ) and (, 2 ), respectively.  2 approximation algorithm. Note that By Theorem 3.1 and Theorem 4.1, we have a pair 1 p( p - 1)  ln  when p  . of (,  ) such that Thus, For any > 0, there exists a constant p such that () = e/(e - 1)(1.118 + ln ),  () = 1 + 0.77/ 1 p( p - 1)  ln  + . for some   1. By letting  = 1.92, we have This completes the proof of the Theorem.   2.803 and   1.402. Therefore, by Theorem 5.1, we get a 2.81-approximation algorithm for the 45 Variants of the 2-LFLP LFLP. A 2.51-approximation algorithm for the 3-LFLP In this section, we present some improved results on can be similarly obtained by using Lemma 3.1, i.e., the approximating some variants of the 2-LFLP. Due to the 1-LFLP can be approximated by a factor of (a, b) = space limit, we state the results and the ideas without (1.104 + ln , 1 + 0.7805/ ) for some  > 1. detailed proof. 5.3 The 2-LFLP with soft capacity This problem 5.1 The two-level concentrator lo cation prob- is the same as the 2-LFLP except that the facility cost lem. In the two-level concentrator location problem (2- for opening facility i is a function of the number of LCLP), we have the same input as that of the 2-LFLP. clients it serves. In particular, if i serves k clients, then However, each client must be served by a first level open the facility cost of i is fi k where fi and ui are given. ui facility only, and each of the first level open facilities for each facility i, there is an upper bound ui on the must be served by a second level open facility. To be number of clients it can serve. It has been shown in precise, we are asked to choose subset  = St  Ft to [5] that the 2-LFLP can be approximated by a factor of open, for t = 1, 2 such that (1.104, 3.56). By Theorem 4.1 and by letting  = 1.281, we obtain a (1.5, 3)-approximation algorithm for the 2j k t2 i min cj k + min cki + f it LFLP. We follow the approach of [25] and show that any iS2 k  S1 =1 t  S t D  S1 (,  )-approximation algorithm for the 2-LFLP implies a (2,  )-approximation algorithm for the 2-LFLP with is minimized. We can apply Algorithm QG to the 2-LCLP as well. soft capacity. Therefore, we obtain a 3-approximation The only change we should make is the construction of algorithm for the 2-LFLP with soft capacity. the instances of the Max-1-LFLP. In particular, when considering a facility i  F2 , the instance of the Max-1LFLP is constructed as follows: the set of clients is D, the set of facilities is F1 , the facility cost for opening facility k  F1 is fk + cki , and the revenue generated by assigning client j to facility k is max{0, Bj - cj k }, where Bj = cj k if j is connected to facility k  F1 , otherwise Bj = j . Then following the same analysis as that for 2-LFLP, we can show that the 2-LCLP can be approximated by a factor of 1.77 in polynomial time. Levin [21] claimed a constant factor approximation algorithm for the k -LCLP when k is a constant. The approximation ratio of his algorithm is exponential on k . Our result significantly improves the ratio when k = 2. 6 Concluding Remarks Serval questions remain open. First of all, although our bound does not depend on the LP relaxation for the 2-LFLP [31], it would be of interest to know the integrality gap of the LP relaxation. A related question is on the lower bound of the 2-LFLP, i.e., whether we can improve it from 1.463 that is the known lower bound for the 1-LFLP. Although in many applications of the multi-level problem, the number of levels is small, it is certainly of theoretical interest to study the approximability of the k -LFLP for general k . Can our technique be extended to the k -LFLP for k  2? This requires a

5.2 The 3- and 4-LFLP In [5], improved algorithms for the k -LFLP have been obtained by reducing it to the 1-LFLP. We generalize this method, and reduce the k -LFLP to the 2-LFLP since we have a strong approximation for the latter problem. In particular, we have the following theorem.

815


good approximation for the maximization version of the (k - 1)-LFLP, which has been studied in [6] and [33]. But their results are not in the form that can be applied within our framework. Finally, our results, if combined with that of Aardal, Chuadk, and Shmoys [2] strongly suggest that it is possible to develop a polynomial time algorithm for the k -LFLP whose performance guarantee depends on k , i.e., the performance guarantee is strictly less than 3 for any k , and converges to 3 when k goes to infinity. Acknowledgement The author would like to thank Yinyu Ye for his support and his feedbacks on preliminary drafts of this paper. The author also thanks Alexander Ageev, Asaf Levin, Pete Veinott, Dachuan Xu and anonymous reviewers for their helpful comments. References

[11]

[12]

[13]

[14]

[15]

[16] [1] K. Aardal, M. Labbe, J. Leung and M. Queyranne, "On the two-level uncapacitated facility location problem," INFORMS Journal on Computing, 8, 289-301, 1996. [2] K. Aardal, F.A. Chudak and D.B. Shmoys, "A 3approximation algorithm for the k-level uncapacitated facility location problem," Information Processing Letters, 72, 161-167, 1999. [3] A. Ageev, "Improved approximation algorithms for multilevel facility location problems," Oper. Res. Letters 30, 327-332, 2002. [4] A. Ageev and M. Sviridenko, "An 0.828-approximation algorithm for uncapacitated facility location problem," Discrete Applied Mathematics, 93, 289-296, 1999. [5] A. Ageev, Y. Ye and J. Zhang, "Improved Combinatorial Apporixmation Algorithms for the k-Level Facility Location Problem," Proceedings of The 30th International Col loquium on Automata, Languages and Programming (ICALP), LNCS 2719, 145-156, 2003. [6] A. Bumb, "An approximation algorithm for the maximization version of the two level uncapacitated facility location problem," Operations Research Letters, 29(4), 155-161, 2001. [7] A.F. Bumb and W. Kern, "A simple dual ascent algorithm for the multilevel facility location problem," 4th International Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX 2001), LNCS 2129, 55-62, 2001. [8] A. I. Barros and M. Labbe, "A general model for the uncapacitated facility and depot location problem," Location Science, 2:173-191, 1994. [9] P. Chardaire, "Facility Location Optimization and Cooperative Games" Ph.d. Thesis, School of Information Systems, University of East-Anglia, Norwich NR4 7TJ, UK, 1998. [10] M. Charikar and S. Guha, "Improved combinatorial algorithms for facility location and k-median problems,"

[17]

[18]

[19]

[20]

[21] [22]

[23]

[24]

[25]

[26]

in Proceedings of the 40th IEEE Foundations of Computer Science (FOCS), 378-388, 1999. C. Chekuri, G. Even and Guy Kortsarz, "A combinatorial approximation algorithm for the group Steiner problem", submitted to Discrete Applied Mathematics. G. Cornu´jols, M.L. Fisher and G.L. Nemhauser, "Loe cation of bank accounts to optimize float: an analytic study of exact and approximate algorithms," Mngt Sci., 23, 789-810, 1977. G. Cornu´jols, G.L. Nemhauser and L.A. Wolsey, "The e uncapacitated facility location problem," in: P. Mirchandani, R. Francis (Eds.), Discrete Location Theory, Wiley, New York, 119-171, 1990. F.A. Chudak and D.B. Shmoys,"Improved approximation algorithms for the uncapacitated facility location problem," SIAM J. on Computing, to appear. N. Edwards, " Approximation algorithms for the multilevel facility location problem," Ph.D. Thesis, School of Operations Research and Industrial Engineering, Cornell University, 2001. J. J. Gao and E.P. Robinson Jr., "A dual-based optimization procedure for the two-echelon uncapacitated facility location problem," Naval Research Logistics, 839:191-212, 1992. J. J. Gao and E.P. Robinson Jr., "Uncapacitated facility location: General solution procedure and computational experience," European Journal of Operational Research, 76:410-427, 1994. S. Guha and S. Khuller, "Greedy strikes back: improved facility location algorithms," Journal of Algorithms, 31: 228-248, 1999. L. Kaufman, M. V. Eede and P. Hansen, "A plant and warehouse location problem," Operations Research Quarterly, 28:547-554, 1977. M. Labbe, "The multi-level uncapacitated facility location problem is not submodular, " European Journal of Operational Research, Vol. 72, 607-609, 1996. A. Levin, Personal Communication, 2003. S. Guha, A. Meyerson and K. Munagala, "Hierarchical placement and network design problems," IEEE Symposium on Foundations of Computer Science (FOCS), 603-612, 2000. K. Jain, M. Mahdian, and A. Saberi, "A new greedy approach for facility location problems," in Proceedings of the 34th ACM Symposium on Theory of Computing (STOC), 731-740, 2002. M. Mahdian, Y. Ye and J. Zhang, "Improved approximation algorithms for metric facility location problems," 5th International Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX 2002), LNCS 2462, 229-242, 2002. M. Mahdian, Y. Ye and J. Zhang, "A 2-approximation algorithm for the soft-capacitated facility location problem," 6th International Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX 2003), LNCS 2764, 129-140, 2003. A. Meyerson, K. Munagala and S. Plotkin, "Costdistance: two-metric network design," IEEE Sympo-

816


[27]

[28]

[29]

[30]

[31]

[32]

[33]

sium on Foundations of Computer Science (FOCS), 624-630, 2000. H. Ro and D. Tcha, "A branch-and-bound algorithm for the two-level uncapacitated facility location problem with some side constraints," European Journal of OPerational Research, 18: 349-358, 1984. E.P. Jr. Robinson and L. Gao, "A new formulation and linear programming based optimization procedure for the two-echelon uncapacitated facility location problem," Annals of the Society of Logistics Engineers, 2, 39-59. E.P. Jr. Robinson, L. Gao and S. D. Muggenborg, "Designing an integrated distribution system at DowBrands, Inc.," Interfaces, 23: 107-117, 1993. D. B. Shmoys, "Approximation algorithms for facility location problems," 3rd International Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX), LNCS 1913, 27-33, 2000. D.B. Shmoys, E. Tardos, and K.I. Aardal, "Approximation algorithms for facility location problems," in Proceedings of the 29th Annual ACM Symposium on Theory of Computing 29th STOC, 265-274, 1997. D. Tcha and B. Lee, "A branch-and-bound algorithm for the multi-level uncapacitated facility location problem," European Journal of Operational Research, 18:35-43, 1984. J. Zhang and Y. Ye, "A Note on the Maximization Version of the Multi-level Facility Location Problem," Operations Research Letters, 30(5), 333-335, 2002.

817