Using Linear Programming in the Design and Analysis of Approximation Algorithms: Two Illustrative Problems David B. Shmoys Cornell University, Ithaca NY 14853, USA Abstract. One of the foremost techniques in the design and analysis of approximation algorithms is to round the optimal solution to a linear programming relaxation in order to compute a near-optimal solution to the problem at hand. We shall survey recent work in this vein for two particular problems: the uncapacitated facility location problem and the problem of scheduling precedence-constrained jobs on one machine so as to minimize a weighted average of their completion times. 1 Introduction One of the most successful techniques in the design and analysis of approximation algorithms for combinatorial optimization problems has been to first solve a relaxation of the problem, and then to round the optimal solution to the relaxation to obtain a near-optimal solution for the original problem. Although the relaxation used varies from problem to problem, linear programming relaxations have provided the basis for approximation algorithms for a wide variety of problems. Throughout this paper, we shall discuss approximation algorithms, where a ρ-approximation algorithm for an optimization problem is a polynomial-time algorithm that is guaranteed to find a feasible solution for the problem with objective function value within a factor of ρ of optimal. In this brief survey, we shall discuss recent developments in the design of approximation algorithms for two specific problems, the uncapacitated facility location problem, and a rather basic single-machine scheduling problem. In focusing on just two problems, clearly we are omitting a great deal of important recent work on a wide cross-section of other problems, but the reader can obtain an accurate indication of the level of activity in this area by considering, for example, the other papers in this proceedings. For a more comprehensive review of the use of this approach, the reader is referred to the volume edited by Hochbaum [16]. We shall consider the following scheduling problem. There are n jobs to be scheduled on a single machine, where each job j has a specified weight wj and processing time pj , j =1,...,n, which we restrict to be positive integers. Furthermore, there is a partial order ≺ that specifies a precedence relation among the jobs; if j ≺ k then we must find a schedule in which job j completes its processing before job k is started. Each job must be processed without interruption, and the machine can process at most one job at a time. If we let Cj denote the completion time of job j, then we wish to minimize the average weighted comple nn tion time wj Cj /n,or equivalently, wj Cj . In the notation of Graham, j=1 j=1 Lawler, Lenstra, & Rinnooy Kan [11], the problem is denoted 1|prec| wj Cj ; it was shown to be NP-hard by Lawler [21]. The first non-trivial approximation algorithm for 1|prec| wj Cj is due to Ravi, Agrawal, & Klein [33], who gave an O(lg nlg W)-approximation algorithm, where W = j wj . A slightly improved performance guarantee of O(lg nlg lg W) follows from work of Even, Naor, Rao, & Schieber [9]. We shall present a series of results that give constant approximation algorithms for this problem, where the resulting algorithms are both simple to state, and simple to analyze. We shall also consider the uncapacitated facility location problem. In this problem, there is a set of locations F at which we may build a facility (such as a warehouse), where the cost of building at location i is fi,for each i∈ F.There is a set D of client locations (such as stores) that require to be serviced by a facility, and if a client at location j is assigned to a facility at location i,a cost of cij is incurred. All of the data are assumed to be non-negative. The objective is to determine a set of locations at which to open facilities so as to minimize the total facility and assignment costs. Building on results for the set covering problem (due to Johnson [19], Lov´asz [25], and Chv´atal [7]), Hochbaum [15] showed that a simple greedy heuristic is an O(log n)-approximation algorithm, where ndenotes the total number of locations in the input. Lin & Vitter [24] gave an elegant filtering and rounding technique that yields an alternate O(log n)-approximation algorithm for this problem. We shall focus on the metric case of this problem, in which distances between locations are given in some metric (and hence satisfy the triangle inequality), and the assignment costs cij are proportional to the distance between i and j,for each i∈ F, j ∈ D. We shall present a series of results that give constant approximation algorithms for this problem, where, once again, the resulting algorithms are both simple to state, and (relatively) simple to analyze. 2 A simple scheduling problem We shall present approximation algorithms for the problem of scheduling precedence- constrained jobs on a single machine so as to minimize the average weighted completion time, 1|prec| wj Cj . Although we will primarily focus on this one scheduling model, the starting point for the work that we shall survey is an extremely simple, elegant result of Phillips, Stein, & Wein [29] for a related problem, in which the jobs are now independent (that is, there are no precedence constraints) but instead each job j has a specified release date rj before which it may not begin processing, j =1,...,n; furthermore, they consider the unit-weight case, or in other words, wj =1, for each j =1,...,n. This problem is denoted 1|rj | Cj and was shown to be NP-hard by Lenstra, Rinnooy Kan, &Brucker [22]. The algorithm of Phillips, Stein, & Wein [29] is based on a relaxation of the problem that can be solved in polynomial time. In this case, however, the relaxation is not a linear program, but instead one motivated in purely scheduling terms: rather than requiring that each job be processed without interruption, we allow preemption. That is, the processing of a job may be interrupted to process another (higher priority) job instead, and then the first job may be resumed without penalty. This problem, denoted 1|rj ,pmtn| Cj ,can be solved (to optimality) by the following simple rule: schedule the jobs in time, and always process the job with the least remaining processing time (among those already released). The approximation algorithm of Phillips, Stein, & Wein works as follows: solve the preemptive relaxation, and then schedule the jobs in the order in which they complete in the relaxed solution. It is remarkably straightforward to show that this is a 2-approximation algorithm. Suppose that the jobs happen to be indexed in the order in which they complete in the preemptive relaxation, and so are processed in the order 1,2,...,n in the heuristically computed non-preemptive schedule as well. If we consider the schedule produced by the approximation algorithm, then any idle time in the schedule ends at the release date of some job k (since that idle time is, in effect, caused by waiting for job k to be released). Consequently, for each job j, there is no idle time between maxk=1,...,j rk and the completion time of job j, Cj . This implies that j Cj ≤ max rk + pj . k=1,...,j k=1 Let Cj denote the completion time of job j in the optimal preemptive schedule; since each job k, k =1,...,j, has completed its processing in the optimal preemptive schedule by Cj , it follows that for each k =1,...,j, j By the same reasoning, k=1 pk ≤ Cj . Hence, Cj ≤ 2Cj .Furthermore,the value n of the schedule found, j=1 Cj , is at most twice the preemptive optimum, and so is at most twice the value of the non-preemptive optimal schedule as well. For 1|prec| wj Cj , we shall rely on a number of linear programming relaxations, but the overall approach will be identical. We will solve the relaxation, and then use the relaxed solution to compute a (natural) ordering of the jobs that is feasible with respect to ≺; this is the schedule computed by the approximation algorithm. This is not the first scheduling problem for which this approach has been considered; for example, Munier & K¨onig [28] have given a very elegant approximation algorithm where the schedule (for a particular parallel machine scheduling problem with communication delays) is derived from an optimal solution to a linear programming relaxation. We start by considering a very strong linear programming relaxation, the non-preemptive time-indexed formulation. In this formulation, which is due to Dyer & Wolsey [8], we use the variable xjt to indicate whether job j completes n processing at time t, j =1,...,n, t=1,...,T,where T = j=1 pj . Given these rk ≤ Ck ≤ Cj , decision variables, it is easy to represent the objective function: nT Minimize wj t· xjt. (1) j=1 t=1 We can constrain the assignments of the decision variables as follows. Each job must complete at a unique point in time; hence, T xjt =1,j =1,...,n. (2) t=1 No job j can complete before pj: xjt =0, if t0, a 4 + -approximation algorithm, and the best-α-point algorithm of Goemans can be adapted to yield a 2 + -approximation algorithm. As it turns out, it is even easier to obtain a 2-approximation algorithm for this problem by using other compact linear programming relaxations. Schulz [35] (and subsequently in its journal version [13]) showed how to improve the earlier work of Hall, Shmoys, & Wein by using a relaxation due to Wolsey [41] and Queyranne [31]. In this formulation, there is a variable Cj for each job j in N = {1,...,n}: n Minimize wj Cj j=1 (9) subject to pj Cj ≥ pj pk, j∈S (j,k)∈S×S for each S ⊆ N, (10) Ck ≥ Cj + pk, if j ≺ k. (11) If the jobs are independent, and hence there are neither precedence constraints nor constraints in (11), then Wolsey [41] and Queyranne [31] independently showed that this linear program provides an exact characterization of the prob lem 1|| wj Cj : extreme points of this linear program correspond to schedules. Of course, in the case in which there are precedence constraints, the situation is quite different, since otherwise P would be equal to NP. The most natural approximation algorithm for 1|prec| wj Cj based on this linear relaxation is as follows: solve the relaxation to obtain a solution Cj , j = 1,...,n, and schedule the jobs so that their LP values are in non-decreasing order. The analysis of this algorithm is also remarkably simple. Suppose that the jobs happen to be indexed so that C1 ≤ ··· ≤ Cn, and so they are scheduled by the algorithm in their index order as well. Once again, job j completes at j time Cj = k=1 pk. If we consider the constraint (10) when S = {1,...,j},then we see that jj pkCk ≥ pkpk ≥ (1/2)( pk)2 . k=1 (k,k )∈S×Sk=1 j j j However, Cj ( k=1 pkCk. Hence Cj ≥ ( k=1 pk)/2, or equivalently, k=1 pk) ≥ Cj ≤ 2Cj . This proves that the value of the solution found is within a factor of 2 of optimal. However, it is not at all clear that this linear programming relaxation is sufficiently more compact than the time-indexed one, since it contains an exponential number of constraints. However, one can solve this linear program in polynomial time with the ellipsoid algorithm, since it is easy to devise a polynomial-time algorithm that determines whether a given fractional solution is feasible, or if not, returns a violated constraint (see Queyranne [31]). Hence, we have a 2-approximation algorithm. Potts [30] has proposed yet another linear programming relaxation of the problem 1|prec| wj Cj , which is called the linear ordering formulation.Inthis formulation, there are variables δij that indicate whether or not job iis processed before job j: n Minimize wj Cj j=1 subject to n pj + i=1 piδij = Cj ,j =1,...,n; δij + δji =1, i,j =1,...,n, ij>k; δij =1, i,j =1,...,n, i≺ j; δij ≥ 0, i,j =1,...,n, i= j. Schulz [35] has observed that for any feasible solution to this linear program, the Cj values are feasible for the linear program (9)–(11). Hence, if we solve the linear ordering formulation to obtain values Cj , and then schedule the jobs so that these values are in non-decreasing order, then we obtain a more efficient 2-approximation algorithm (since any polynomial-time linear programming algorithm can be used to solve this LP with n2 variables and O(n3) constraints). Chudak & Hochbaum [5] proposed a somewhat weaker linear programming relaxation, which also uses the variables δij . In this relaxation, the constraints that enforce the transitivity of the ordering relaxation, δij + δjk + δki ≤ 2, are instead replaced with the constraints that δki ≤ δkj , whenever i ≺ j,and k is different from both jobs i and j. Once again, a straightforward calculation shows that for any feasible solution to this weaker linear program, the Cj values are feasible for the constraints (10) and (11). Consequently, one also obtains a 2-approximation algorithm by first solving this weaker linear program, and then using the resulting Cj values to order the jobs. The advantage of using this formulation is as follows: Chudak & Hochbaum also observed that a result of Hochbaum, Meggido, Naor, & Tamir [17] can be applied to show that there always exists an optimal solution to this linear program that is half-integral, i.e., each variable δij is either 0,1/2, or 1; furthermore, an optimal half-integral solution can be computed by a maximum flow computation. Thus, this approach yields a 2-approximation algorithm that does not require the solution of a linear program, but rather only a single maximum flow computation. Chekuri & Motwani [2] and Margot, Queyranne, & Wang [27] independently devised another, more combinatorial 2-approximation algorithm for the problem 1|prec| wj Cj . We shall say that a subset S of jobs is an initial set of the precedence relation ≺ if, for each job k ∈ S, each of its predecessors is also in S, or more formally, (k ∈ S and j ≺ k) ⇒ j ∈ S. For each subset of jobs S ⊆ N,let ρ(S)= j∈S pj / j∈S wj . Suppose that we minimize ρ(S) over all initial subsets to obtain a subset S∗ . Chekuri & Motwani and Margot, Queyranne, & Wang proved a remarkable fact: if S∗ = N,then any ordering of the jobs that is consistent with ≺ has objective function value within a factor of 2 of the optimum. The proof of this fact is amazingly simple. In each feasible schedule, each job j completes by time k∈N pk, and so the cost of any solution is at most ( k∈N pk)( k∈N wk ). So we need only show that the optimal value is at least ( k∈N pk)( k∈N wk)/2. Suppose that the jobs happen to be indexed so that job j is the jthjob to be scheduled in an optimal schedule. Then each set {1,...,j} is an initial set, and hence the completion time of job j, jj Cj = pk ≥ ρ(N) wk . k=1 k=1 Consequently, we know that nnj n wj Cj ≥ ρ(N) wj wk ≥ ρ(N)( wj )2/2. j=1 j=1 k=1 j=1 nn Recalling that ρ(N)= j=1 pj / j=1 wj , we see that we have obtained the desired lower bound on the optimal value. Of course, there is no reason to believe that N is the initial set S for which ρ(S) is minimized. Fortunately, if this is not the case, then we can rely on the following decomposition result of Sidney [37]: if S∗ is the initial set S for which ρ(S) is minimized, then there exists an optimal solution in which the jobs of S∗ precede the jobs of N −S∗ . This suggests the following recursive 2-approximation algorithm: find the set S∗ , and schedule it first in any order consistent with the precedence relation ≺, and then recursively apply the algorithm to N − S∗,and concatenate the two schedules found. It is not hard to show that the initial set S∗ can be found via a minimum cut (or equivalently, a maximum flow) computation. For each of the results above, we have presented an algorithm and then showed that it delivers a solution whose objective function value is within some constant factor of the optimal value of a linear programming relaxation of the problem. Such a result not only shows that we have found a good algorithm, but also implies a guarantee for the quality of the lower bound provided by that linear program. For each of the linear programs concerned, one might ask whether these particular algorithms can be improved; that is, might it be possible to round the optimal fractional solutions in a more effective manner? Unfortunately, the answer to each of these questions is no. For the time-indexed formulation, Schulz & Skutella [34] have given instances for which the ratio between the integer and fractional optima is arbitrarily close to 2. For the linear ordering formulation, Chekuri & Motwani [2] have given a surprising construction based on expander graphs for which the ratio of the integer to fractional optimal values asymptotically approaches 2. Each of these results implies the analogous result for the linear program (9)–(11), but for this relaxation it is also relatively simple to construct examples directly. Of course, there might still be other relaxations that provide stronger lower bounds, and this is an extremely interesting direction for further research. 3 The uncapacitated facility location problem The uncapacitated facility location problem is one of the most well-studied problems in the Operations Research literature, dating back to the work of Balinski [1], Kuehn & Hamburger [20], Manne [26], and Stollsteimer [38, 39] in the early 60’s. We shall focus on one important special case of this problem, where the locations are embedded in some metric space, and the assignment costs cij are proportional to the distances between locations; we shall call this the metric uncapacitated facility location problem. Although there is little work that has specifically focused on the metric case of this location problem, for many others, such as the k-center problem (see, e.g., [18]) and the k-median problem (see, e.g., [23]) this assumption is prevalent. In fact, the algorithms of Lin & Vitter [23] contained many of the seeds of the work that we shall present for the metric uncapacitated facility location problem. Once again, all of the algorithms that we shall discuss will be based on rounding an optimal solution to a linear programming relaxation of the problem. For this problem, the most natural relaxation is as follows. There are two types of decision variables xij and yi,for each i ∈ F , j ∈ D, where each variable yi, i ∈ F , indicates whether or not a facility is built at location i,and each variable xij indicates whether or not the client at location j is assigned to a facility at location i,for each i ∈F , j ∈D: Minimize fiyi + cij xij i∈F i∈F j∈D (12) subject to xij =1, i∈F for each j ∈D, (13) xij ≤yi, for each i ∈ F, j ∈ D, (14) xij ≥0, for each i ∈ F, j ∈D. (15) Shmoys, Tardos, & Aardal [36] gave a simple algorithm to round an optimal solution to this linear program to an integer solution of cost at most 3/(1−e3) ≈ 3.16 times as much. The algorithm relies on the filtering technique of Lin & Vitter [24]. We can interpret each fractional solution (x, y) as the following bipartite graph G(x, y)=(F, D, E): the two sets of nodes are F and D,and there is an edge (i, j) ∈E exactly when xij > 0. First, we apply an α-filtering algorithm to convert the optimal fractional solution to a new one, (¯x, y¯), in which the cost cij associated with each edge in G(¯x, y¯) is relatively cheap. As in the algorithm based on the time-indexed formulation for the scheduling problem, we first define the notion of an α-point, cj (α), for each location j ∈ D. Focus on a location j ∈ D,and let be a permutation such that cπ(1)j ≤cπ(2)j ≤···≤cπ(n)j. We then set cj (α)= cπ(i∗)j , i where i ∗ =min{i : ≥ α}. To construct (¯x, y¯), for each (i, j) ∈ i=1 xπ(i)j E(x, y)for which cij >cj (α)we set x¯ ij = 0, and then renormalize by setting each remaining x¯ ij equal to xij /αj ,where αj = (i,j)∈E: cij ≤cj (α) xij .Wealso renormalize y¯ i = yi/α. It is easy to check that (¯x, y¯) is a feasible solution to the linear program (12)–(15) with the further property that x¯ ij > 0 ⇒ cij ≤ cj (α). Motivated by this, given values gj , j ∈ D, we shall call a solution g-close if x¯ ij > 0 ⇒cij ≤gj . The central element of the rounding algorithm of Shmoys, Tardos, & Aardal is a polynomial-time algorithm that, given a g-close feasible solution (¯x, y¯)to (12)–(15), finds a 3g-close integer solution (ˆx, yˆ) such that fiyˆi ≤ fiy¯ i. i∈Fi∈F The algorithm works as follows. It partitions the graph G(¯x, y¯)= (F, D, E)into clusters, and then, for each cluster, opens one facility that must serve all clients in it. The clusters are constructed iteratively as follows. Among all clients that have not already been assigned to a cluster, let j be the client j for which gj is smallest. This cluster consists of j , all neighbors of j in G(¯x, y¯), and all of their neighbors as well (that is, all nodes j such that there exists some i for which (i, j)and (i, j )are both in E. Within this cluster, we open the cheapest facility i and use it to serve all clients within this cluster. We next show that this rounding algorithm has the two claimed properties. Each client j in the cluster is assigned to a facility i for which there is a path in G(¯x, y¯) consisting of an edge connecting i and j (of cost at most gj ), an edge connecting j and some node i (ofcostatmost gj ), andanedgeconnecting i and j (ofcostatmost gj ). Hence, by the triangle inequality, the cost of assigning j to i is at most 2gj + gj .Since j was chosen as the remaining client with minimum g-value, it follows that gj ≤ gj , and so the cost of assigning j to i is at most 3gj . In other words, the integer solution found is 3g-close. Consider the first cluster formed, and let j be the node with minimum g value used in forming it. We know that x¯ ij = 1. Since the minimum i:(i,j )∈E of a set of values is never more than a weighted average of them, the cost of the facility selected fi ≤ x¯ ij fi ≤ y¯ ifi, i:(i,j )∈Ei:(i,j )∈E where the last inequality follows from constraint (14). Observe that, throughout the execution of the algorithm, each location j ∈ D that has not yet been assigned to some cluster, has the property that each of its neighbors i must also remain unassigned. Hence, for each cluster, the cost of its open facility is at most the cost that the fractional solution assigned to nodes in F within that cluster. Hence, in total, fiyˆi ≤ fiy¯ i. i∈Fi∈F Thus, we have argued that the rounding algorithm of Shmoys, Tardos, & Aardal has the two key properties claimed above. Suppose that we apply this rounding theorem to an α-filtered solution. What can we prove about the cost of the resulting integer solution? By the two properties proved above, we know that the cost of the solution is at most fiyˆi + cij xˆij ≤ fiy¯ i +3cj (α)= fiyi/α +3 cj (α). i∈Fi∈Fj∈Di∈Fj∈Di∈Fj∈D However, exactly analogous to (8), we again know that at most a (1−α)fraction of the values in a weighted average can exceed 1/(1 − α) times the average, and hence cj (α) ≤ ( cij xij )/(1 − α). i∈D Plugging this bound into the previous inequality, we see that the total cost of the solution found is at most 13 max{ , }( fiyi + cij xij ). α 1 − α i∈Fi∈Fj∈D If we set α =1/4, then we see that the total cost of the solution found is at most 4times the cost of (x, y), and so by rounding an optimal solution to the linear relaxation, we obtain a 4-approximation algorithm. Once again, we may apply the idea of Goemans [10]; it is foolish to set α once, rather than choosing the best α for each input. Once again, we will analyze this best-α algorithm by analyzing a randomized algorithm instead. Let 0 <β< 1be a parameter to be fixed later. We shall set α = a,where a is selected uniformly at random within the interval [β, 1]. Once again, we shall rely on the fact that 1 n cj (a)da = cij xij . 0 i=1 The expected cost of the solution found can be upper bounded by 11 E[ fiyi +3 cj (a)] = E[] fiyi +3 E[cj (a)] aa i∈Fj∈Di∈Fj∈D 1 1 11 1 =( da) fiyi +3 ( cj (a)da) β 1 −βa β 1 −β i∈Fj∈D 1 ln(1/β)3 ≤ fiyi + cj (a)da 1 −β 1 −β 0 i∈Fj∈D ln(1/β)3 = fiyi + cij xij . 1 −β 1 −β i∈Fj∈Di∈F 3 If we set β =1/e3 , then we have obtained the claimed 3 -approximation 1−e algorithm. Guha & Khuller [12] proposed the following improvement to the algorithm of Shmoys, Tardos, & Aardal. A natural way in which to compute a better solution is to perform a post-processing phase in which one iteratively checks if an additional facility can be opened to reduce the overall cost, and if so, greedily opens the facility that most reduces the total cost. Furthermore, Guha & Khuller also proposed the following strengthening of the linear programming relaxation. If one knew the cost φ incurred to build facilities in the optimal so lution, one could add the constraint that i∈F fiyi ≤ φ. Since we don’t know this value, we can instead guess this value by setting φ equal to (1+ )k,for each k =1,..., log1+ fi,where is an arbitrarily small positive constant. i∈F There are only a polynomial number of settings for φ that must be considered, and so, in effect, we may assume that we know the correct φ to an arbitrary number of digits of accuracy. By adding the post-processing phase to the result of applying the rounding algorithm to the strengthened relaxation, Guha & Khuller obtain a 2.408-approximation algorithm. Guha & Khuller [12] and Sviridenko [40] independently showed that this problem is MAXSNP-hard, and hence there exists some constant ρ> 1for which no ρ-approximation algorithm exists, unless P = NP. Guha & Khuller also showed a much stronger result, that no approximation algorithm can have performance guarantee better than O(log log n))). 1.463 (unless NP ⊆ DT IME(n Chudak & Shmoys, independently, obtained a more modest improvement, a 3-approximation algorithm, which relies only on the original linear programming relaxation. The first essential idea in their improvement was the observation that the filtering step is, in some sense, completely unnecessary for the performance of the algorithm. This was based on a simple property of the optimal solution to the linear programming relaxation. Consider the dual to the linear program (12)–(15): Maximize vj (16) j∈D subject to wij ≤ fi, for each i ∈ F, j∈D vj − wij ≤ cij , for each i ∈ F, j ∈ D, wij ≥ 0 for each i ∈ F, j ∈ D. This dual can be motivated in the following way. Suppose that we wish to obtain a lower bound for our input to the uncapacitated facility location problem. If we reset all fixed costs fi to 0, and solve this input, then clearly we get a (horrible) lower bound: each client j ∈ D gets assigned to its closest facility at a cost of mini∈F cij . Now suppose we do something a bit less extreme. Each location i ∈ F decides on a given cost-sharing of its fixed cost fi. Each location j ∈ D is allocated a share wij of the fixed cost; if j is assigned to an open facility at i, then it must pay an additional fee of wij (for a total of cij + wij ), but the explicit fixed cost of i is once again reduced to 0. Of course, we insist that each wij ≥ 0, and j∈D wij ≤ fi for each i ∈ F . But this is still an easy input to solve: each j ∈ D incurs a cost vj =mini∈F (cij + wij ), and the lower bound is j∈D vj . Of course, we want to allocate the shares so as to maximize this lower bound, and this maximization problem is precisely the LP dual. Consider a pair of primal and dual optimal solutions: (x, y)and (v, w). Complementary slackness implies that if xij > 0, then the corresponding dual constraint is satisfied with equality. That is, vj − wij = cij , and since wij ≥ 0, we see that cij ≤ vj ;inother words, (x, y)is already v-close. Hence, if we apply the rounding algorithm of Shmoys, Tardos, & Aardal (without filtering first, and so gj = vj ), we find a solution of cost at most fiyi+3vj = fiyi+3( fiyi+ cij xij ) ≤ 4( fiyi+ cij xij ), i∈Fj∈Di∈Fi∈Fi∈Fj∈Di∈Fi∈Fj∈D where the first equality follows from the fact that the optimal solutions to the primal and the dual linear programs have equal objective function values. The second key idea in the improvement of Chudak & Shmoys was the use of randomized rounding in the facility selection step. Randomized rounding is an elegant technique introduced by Raghavan & Thompson [32], in which a feasible solution to a linear programming relaxation of a 0–1 integer program is rounded to an integer solution by interpreting the fractions as probabilities, and setting each variable to 1 with the corresponding probability. Sviridenko [40] proposed a simple randomized rounding approximation algorithm for the special case of the metric uncapacitated facility location problem in which each cij ∈{1, 2}.In the deterministic algorithm presented above, the cheapest facility in each cluster was opened. Instead, if the cluster is “centered” at j , one can open facility i with probability xij . This does not really change the previous analysis, since the expected cost of the facilities selected is at most fiyi, and the bound i∈F on the assignment costs was independent of the choice of the facility opened in each cluster. The final idea used to obtain the improved performance guarantee is as follows: rather than select the next center by finding the remaining client for which vj is minimum (since gj = vj in the version without filtering), select the client for which vj + i∈F cij xij is minimum. This enters into the analysis in the following way. For each client j in the cluster “centered” at j , its assignment cost is bounded by the cost of an edge (i, j) (of cost at most vj ), an edge (i, j )(of cost at most vj ), and the edge (i ,j ). The last of these costs is a random variable, and so we can focus on its expected value. Since j chooses to open each facility i with probability xij , the expected cost of the edge (i ,j )is exactly i∈F cij xij . Thus, the expected cost of assigning j to i is at most vj + vj + i∈F cij xij . By our modified selection rule, this expectation is at most 2vj + i∈F cij xij , and hence the expected total cost of the solution is at most 2vj + cij xij + fiyi, j∈Dj∈Di∈Fi∈F which is exactly equal to three times the optimal value of the linear programming relaxation. The analogous deterministic algorithm is quite natural. Before, we merely chose the cheapest facility in each cluster. However, by choosing a facility, we also affect the assignment cost of each client in that cluster. Thus, if choose the facility that minimizes the total cost for that cluster,then weachieve a deterministic 3-approximation algorithm. However, this is not the best possible analysis of this randomized algorithm. Subsequently, Chudak [4] and Chudak & Shmoys [6] have improved this bound to show that (essentially) this randomized algorithm leads to a (1 + 2/e)approximation algorithm. We shall modify the algorithm in the following way. For each location i ∈ F , there is some probability pi with which it has been opened by this algorithm. (For most locations, it is equal to some value xij when facility location i belongs to a cluster “centered” at j , but some locations i might not belong to any cluster.) In the modified algorithm, we also have independent events that open each facility i with probability yi −pi.Infact, we can simplify some of this discussion by making the following further assumption about the optimal solution (x, y) to the linear program (12)–(15): for each xij > 0, it follows that xij = yi. We shall say that such a solution is complete. This assumption can be made without loss of generality, since it is not hard to show that for any input, there is an equivalent input for which the optimal fractional solution is complete. For the algorithms above, we have indicated that each client is assigned to the facility that has been opened in its cluster. In fact, there is no need to make this assumption about the assignments, since we may simply assign each client to its cheapest open facility. Given this, the key insight to the improved analysis is as follows. Consider some client j (which is not the center of its cluster). We have shown that its assignment cost is at most 3vj (for the 4-approximation algorithm, and a somewhat better bound for the 3-approximation algorithm). However, the randomized algorithm might very well open one of j’s neighbors in G(x,y). In that case, clearly we can obtain a much better bound on the assignment cost incurred for client j. In fact, one can show that the probability that a facility has been opened at least one of j’s neighbors is at least (1 −1/e), and this is the basic insight that leads to the improved analysis. Although the complete analysis of this algorithm is beyond the scope of this survey, we will outline its main ideas. The improvement in the bound is solely due to the fact that we can bound the expected assignment cost for each client j by i∈F cij xij +(2/e)vj. In fact, we will only sketch the proof that this expectation is at most i∈F cij xij +(3/e)vj , and will use as a starting point, the original clustering algorithm in which the next client selected is the one for which vj is smallest (rather than the modified one in which selection was based on vj + i∈F cij xij ). Suppose that the neighbors of client j in G(x,y)happento benodes 1,...,d, d d where c1j ≤ ··· ≤ cdj .Thus, = = 1. Wecan bound theex i=1 xij i=1 yi pected assignment cost for j, by considering nodes i=1,...,din turn, assigning j to the first of these that has been opened, and if none of these facilities have been opened, then assigning j to the “back-up” facility i that has surely been opened in its cluster. If opening neighboring facilities i=1,...,d were independent events, then a simple upper bound on the expected assignment cost for j is y1c1j +(1 −y1)y2c2j + ···+(1 −y1) ···(1 −yd−1)ydcdj +(1 −y1) ···(1 −yd)3vj , d d which is clearly at most i=1 cij yi+3vj (1−yi).The Taylor series expansion i=1 −r −r of e implies that 1 −r ≤ e . Using this fact, and the assumption that the optimal LP solution (x,y) is complete, we see that the expected assignment cost for j is at most i∈F cij xij +(3/e)vj . However, opening the neighboring facilities i=1,...,d are not independent events: for instance, if two of these neighbors are in the same cluster, then only one of them can be opened. The next question is: can the conditioning between these events be harmful? Fortunately, the answer is no, and it is fairly intuitive to see why this is the case. If it happens that none of the first k neighbors of j have not been opened, this only makes it more likely that the next cheapest facility is, in fact, open. A precise analysis of this situation can be given, and so one can prove that the expected assignment cost for j is at most i∈F cij xij +(3/e)vj (without relying on unsupportable assuptions). These randomized approximation algorithms can each be derandomized, by a straightforward application of the method of conditional probabilities. Thus, if we return to the selection rule in which the next cluster is “centered” at the remaining client j for which vj + i∈F cij xij is minimized, then this derandomization leads to a (1 + 2/e)-approximation algorithm. For the uncapacitated facility location problem, the natural questions for further research are even more tantalizing than for the scheduling problem discussed in the previous section. It is not known that the analysis of the algorithm of Chudak & Shmoys is tight (and in fact, we suspect that it is not tight). Guha & Khuller [12] have given an input for which the ratio between the optimal integer and fractional optima is at least 1.463, but this still leaves some room between that and the upper bound of 1 + 2/e ≈ 1.736 implied by the last algorithm. Furthermore, there are well-known ways to construct stronger linear programming relaxations for this problem, and it would be very interesting to use them to prove stronger performance guarantees. References 1. M. L. Balinksi. On finding integer solutions to linear programs. In Proceedings of the IBM Scientific Computing Symposium on Combinatorial Problems, pages 225–248. IBM, 1966. 2. C. Chekuri and R. Motwani. Precedence constrained scheduling to minimize weighted completion time on a single machine. Unpublished manuscript, 1997. 3. C. Chekuri, R. Motwani, B. Natarajan, and C. Stein. Approximation techniques for average completion time scheduling. Proceedings of the Eighth Annual ACMSIAM Symposium on Discrete Algorithms, pages 609–618, 1997. 4. F. A. Chudak. Improved approximation algorithms for uncapacitated facility location. In: Proceedings of the 6th Integer Programming and Combinatorial Optimization Conference (IPCO), 1998, to appear. 5. F. A. Chudak and D. S. Hochbaum. A half-integral linear programming relaxation for scheduling precedence-constrained jobs on a single machine. Unpublished manuscript, 1997. 6. F. A. Chudak and D. B Shmoys. Improved approximation algorithms for the uncapacitated facility location problem. Unpublished manuscript, 1997. 7. V. Chv´atal. A greedy heuristic for the set covering problem. Math. Oper. Res., 4:233–235, 1979. 8. M. E. Dyer and L. A. Wolsey. Formulating the single machine sequencing problem with release dates as a mixed integer program. Discrete Appl. Math., 26:255–270, 1990. 9. G. Even, J. Naor, S. Rao, and B. Schieber. Divide-and-conquer approximation algorithms via spreading metrics. In Proceedings of the 36th Annual IEEE Symposium on Foundations of Computer Science, pages 62–71, 1995. 10. M. X. Goemans. Personal communication, June, 1996. 11. R. L. Graham, E. L. Lawler, J. K. Lenstra, and A. H. G. Rinnooy Kan. Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann. Discrete Math., 5:287–326, 1979. 12. S. Guha and S. Khuller. Greedy strikes back: Improved facility location algorithms. In Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 649–657, 1998. 13. L. A. Hall, A. S. Schulz, D. B. Shmoys, and J. Wein. Scheduling to minimize the average completion time: on-line and off-line approximation algorithms. Math. Oper. Res., 22:513–544, 1997. 14. L. A. Hall, D. B. Shmoys, and J. Wein. Scheduling to minimize the average completion time: on-line and off-line algorithms. In Proceedings of the 7th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 142–151, 1996. 15. D. S. Hochbaum. Heuristics for the fixed cost median problem. Math. Programming, 22:148–162, 1982. 16. D. S. Hochbaum, editor. Approximation algorithms for NP-hard problems,Boston, MA, 1997. PWS. 17. D. S. Hochbaum, N. Megiddo, J. Naor, and A. Tamir. Tight bounds and 2approximation algorithms for integer programs with two variables per inequality. Math. Programming, 62:69–83, 1993. 18. D. S. Hochbaum and D. B. Shmoys. A best possible approximation algorithm for the k-center problem. Math. Oper. Res., 10:180–184, 1985. 19. D. S. Johnson. Approximation algorithms for combinatorial problems. J. Comput. System Sci., 9:256–278, 1974. 20. A. A. Kuehn and M. J. Hamburger. A heuristic program for locating warehouses. Management Sci., 9:643–666, 1963. 21. E. L. Lawler. Combinatorial Optimization: Networks and Matroids.Holt, Rinehart, and Winston, New York, 1976. 22. J. K. Lenstra, A. H. G. Rinnooy Kan, and P. Brucker. Complexity of machine scheduling problems. Ann. Discrete Math., 1:343–362, 1977. 23. J.-H. Lin and J. S. Vitter. Approximation algorithms for geometric median problems. Inform. Proc. Lett., 44:245–249, 1992. 24. J.-H. Lin and J. S. Vitter. -approximations with minimum packing constraint violation. In Proceedings of the 24th Annual ACM Symposium on Theory of Computing, pages 771–782, 1992. 25. L. Lov´asz. On the ratio of optimal integral and fractional covers. Discrete Math., 13:383–390, 1975. 26. A. S. Manne. Plant location under economies-of-scale-decentralization and computation. Management Sci., 11:213–235, 1964. 27. F. Margot, M. Queyranne, and Y. Wang. Decompositions, network flows and a precedence constrained single machine scheduling problem. Unpublished manuscript, December, 1996. 28. A. Munier and J. C. K¨onig. A heuristic for a scheduling problem with communication delays. Oper. Res., 45:145–147, 1997. 29. C. A. Phillips, C. Stein, and J. Wein. Minimizing average completion time in the presence of release dates. Math. Programming B, 1998. To appear. 30. C. N. Potts. An algorithm for the single machine sequencing problem with precedence constraints. Math. Programming Stud., 13:78–87, 1980. 31. M. Queyranne. Structure of a simple scheduling polyhedron. Math. Programming, 58:263–285, 1993. 32. P. Raghavan and C. D. Thompson. Randomized rounding: a technique for provably good algorithms and algorithmic proofs. Combinatorica, 7:365–374, 1987. 33. R. Ravi, A. Agrawal, and P. Klein. Ordering problems approximated: single- processor scheduling and interval graph completion. In Proceedings of the 18th International Colloquium on Automata, Languages, and Processing, Lecture Notes in Computer Science 510, pages 751–762, 1991. 34. A. S. Schulz and M. Skutella. Personal communication, 1997. 35. A. S. Schulz. Scheduling and Polytopes. PhD thesis, Technical University of Berlin, 1996. ´ 36. 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, pages 265–274, 1997. 37. J. B. Sidney. Decomposition algorithms for single-machine sequencing with precedence and deferral costs. Oper. Res., pages 283–298, 1975. 38. J. F. Stollsteimer. The effect of technical change and output expansion on the optimum number, size and location of pear marketing facilities in a California pear producing region. PhD thesis, University of California at Berkeley, Berkeley, California, 1961. 39. J. F. Stollsteimer. A working model for plant numbers and locations. J. Farm Econom., 45:631–645, 1963. 40. M. Sviridenko. Personal communication, July, 1997. 41. L. A. Wolsey. Mixed integer programming formulations for production planning and scheduling problems. Invited talk at the 12th International Symposium on Mathematical Programming, MIT, Cambridge, August, 1985. This article was processed using the LaTEX macro package with LLNCS style