New Approximation Algorithms for the Unsplittable Capacitated Facility Location Problem

In this paper, we consider the Unsplittable (hard) Capacitated Facility Location Problem (UCFLP) with uniform capacities and present new approximation algorithms for it. This problem is a generalization of the classical facility location problem where each facility can serve at most u units of demand and each client must be served by exactly one facility. This problem is motivated by its applications in many practical problems including supply chain problems of indivisible goods (Verter in Foundations of location analysis, chapter 2. International series in operations research and management science. Springer, Berlin, 2011) and the assignment problem in the content distribution networks (Bateni and Hajiaghayi in Proceedings of the nineteenth annual ACM-SIAM symposium on discrete algorithms, pp 805–814, 2009). While there are several approximation algorithms for the soft capacitated version of this problem (in which one can open multiple copies of each facility) or the splittable version (in which the demand of each client can be divided to be served by multiple open facilities), there are very few results for the UCFLP. It is known that it is NP-hard to approximate this problem within any factor without violating the capacities. So we consider bicriteria $$(\alpha ,\beta )$$(α,β)-approximations where the algorithm returns a solution whose cost is within factor $$\alpha $$α of the optimum and violates the capacity constraints within factor $$\beta $$β. Shmoys et al. (Proceedings of the twenty-ninth annual ACM symposium on theory of computing, pp 265–274, 1997) were the first to consider this problem and gave a (9, 4)-approximation. Later results imply (O(1), 2)-approximations, however, no constant factor approximation is known with capacity violation of less than 2. We present a framework for designing bicriteria approximation algorithms for this problem and show two new approximation algorithms with factors (9, 3 / 2) and (29.315, 4 / 3). These are the first algorithms with constant approximation in which the violation of capacities is below 2. The heart of our algorithm is a reduction from the UCFLP to a restricted version of the problem. One feature of this reduction is that any $$(O(1),1+{\epsilon })$$(O(1),1+ϵ)-approximation for the restricted version implies an $$(O(1),1+{\epsilon })$$(O(1),1+ϵ)-approximation for the UCFLP and we believe our techniques might be useful towards finding such approximations or perhaps $$(f({\epsilon }),1+{\epsilon })$$(f(ϵ),1+ϵ)-approximation for the UCFLP for some function f. In addition, we present a quasi-polynomial time $$(1+\epsilon ,1+\epsilon )$$(1+ϵ,1+ϵ)-approximation for the (uniform) UCFLP in Euclidean metrics, for any constant $${\epsilon }>0$$ϵ>0.

Related papers:

title: Facility location - applications and theory
abstract: 1 The Weber Problem.- 2 Continuous Covering Location Problems.- 3 Discrete Network Location Models.- 4 Location Problems in the Public Sector.- 5 Consumers in Competitive Location  6 An Efficient Genetic Algorithm for the p-Median Problem.- 7 Demand Point Aggregation for Location Models.- 8 Location Software and Interface with GIS and Supply Chain Management.- 9 Telecommunication and   Problems with Stochastic Demands and Congestion.- 12 Hub Location Problems.- 13 Location and Robotics.- 14 The Quadratic Assignment Problem.

title: Assignment problem in content distribution networks: Unsplittable hard-capacitated facility location
abstract: In a Content Distribution Network (CDN), there are m servers storing the data; each of them has a specific bandwidth. All the requests from a particular client should be assigned to one server because of the routing protocol used. The goal is to minimize the total cost of these assignments—cost of each is proportional to the distance between the client and the server as well as the request size—while the load on each server is kept below its bandwidth limit. When each server also has a setup cost, this is an unsplittable hard-capacitated facility location problem. As much attention as facility location problems have received, there has been no nontrivial approximation algorithm when we have hard capacities (i.e., there can only be one copy of each facility whose capacity cannot be violated) and demands are unsplittable (i.e., all the demand from a client has to be assigned to a single facility). We observe it is NP-hard to approximate the cost to within any bounded factor in this case. Thus, for an arbitrary constant ε>0, we relax the capacities to a 1+ε factor. For the case where capacities are almost uniform, we give a bicriteria O(log n, 1+ε)-approximation algorithm for general metrics and a (1+ε, 1+ε)-approximation algorithm for tree metrics. A bicriteria (α,β)-approximation algorithm produces a solution of cost at most α times the optimum, while violating the capacities by no more than a β factor. We can get the same guarantees for nonuniform capacities if we allow quasipolynomial running time. In our algorithm, some clients guess the facility they are assigned to, and facilities decide the size of the clients they serve. A straightforward approach results in exponential running time. When costs do not satisfy metricity, we show that a 1.5 violation of capacities is necessary to obtain any approximation.
 It is worth noting that our results generalize bin packing (zero connection costs and facility costs equal to one), knapsack (single facility with all costs being zero), minimum makespan scheduling for related machines (all connection costs being zero), and some facility location problems.

title: Analysis of a local search heuristic for facility location problems
abstract: In this paper, we study approximation algorithms for several NP-hard facility location problems. We prove that a simple local search heuristic yields polynomial-time constant-factor approximation bounds for the metric versions of the uncapacitated k-median problem and the uncapacitated facility location problem. (For the k-median problem, our algorithms require a constant-factor blowup in the parameter k.) This local search heuristic was first proposed several decades ago, and has been shown to exhibit good practical performance in empirical studies. We also extend the above results to obtain constant-factor approximation bounds for the metric versions of capacitated k-median and facility location problems.

title: A Multiexchange Local Search Algorithm for the Capacitated Facility Location Problem
abstract: We present a multiexchange local search algorithm for approximating the capacitated facility location problem (CFLP), where a new local improvement operation is introduced that possibly exchanges multiple facilities simultaneously. We give a tight analysis for our algorithm and show that the performance guarantee of the algorithm is between 3+2v2-e and 3+2v2+e for any given constant e>0. The previously known best approximation ratio for the CFLP is 7.88, as shown by Mahdian and PAil (2003. Universal facility location. Algorithms (ESA), 409--421), based on the operations proposed by PAil et al. (2001. Facility location with hard capacities. . Our upper bound 3+2v2+e also matches the best-known ratio, obtained by Chudak and Williamson (1999.Improved approximation algorithm for capacitated facility location problems. , for the CFLP with uniform capacities. In order to obtain the tight bound of our new algorithm, we make interesting use of the notion of exchange graph of PAil et al. and techniques from the area of parallel machine scheduling.

title: A 3-Approximation for Facility Location with Uniform Capacities
abstract: We consider the facility location problem where each facility can serve at most U clients. We analyze a local search algorithm for this problem which uses only the operations of add, delete and swap and prove that any locally optimum solution is no more than 3 times the global optimum. This improves on a result of Chudak and Williamson who proved an approximation ratio of $3+2\sqrt{2}$ for the same algorithm. We also provide an example which shows that our analysis is tight.

title: Anycast CDNS revisited
abstract: Because it is an integral part of the Internet routing apparatus, and because it allows multiple instances of the same service to be "naturally" discovered, IP Anycast has many attractive features for any service that involve the replication of multiple instances across the Internet. While briefly considered as an enabler when content distribution networks (CDNs) first emerged, the use of IP Anycast was deemed infeasible in that environment. The main reasons for this decision were the lack of load awareness of IP Anycast and unwanted side effects of Internet routing changes on the IP Anycast mechanism. Prompted by recent developments in route control technology, as well as a better understanding of the behavior of IP Anycast in operational settings, we revisit this decision and propose a load-aware IP Anycast CDN architecture that addresses these concerns while benefiting from inherent IP Anycast features. Our architecture makes use of route control mechanisms to take server and network load into account to realize load-aware Anycast. We show that the resulting redirection requirements can be formulated as a Generalized Assignment Problem and present practical algorithms that address these requirements while at the same time limiting session disruptions that plague regular IP Anycast. We evaluate our algorithms through trace based simulation using traces obtained from an operation CDN network.

title: A tight bound on approximating arbitrary metrics by tree metrics
abstract: In this paper, we show that any n point metric space can be embedded into a distribution over dominating tree metrics such that the expected stretch of any edge is O(log n). This improves upon the result of Bartal who gave a bound of O(log n log log n). Moreover, our result is existentially tight; there exist metric spaces where any tree embedding must have distortion Ω(log n)-distortion. This problem lies at the heart of numerous approximation and online algorithms including ones for group Steiner tree, metric labeling, buy-at-bulk network design and metrical task system. Our result improves the performance guarantees for all of these problems.

title: e-approximations with minimum packing constraint violation (extended abstract)
abstract: We present efficient new randomized and deterministic methods for transforming optimal solutions for a type of relaxed integer linear program into provably good solutions for the corresponding NP-hard discrete optimization problem. Without any constraint violation, the ε-approximation problem for many problems of this type is itself NP-hard. Our methods provide polynomial-time ε-approximations while attempting to minimize the packing constraint violation.
Our methods lead to the first known approximation algorithms with provable performance guarantees for the s-median problem, the tree prunning problem, and the generalized assignment problem. These important problems have numerous applications to data compression, vector quantization, memory-based learning, computer graphics, image processing, clustering, regression, network location, scheduling, and communication. We provide evidence via reductions that our approximation algorithms are nearly optimal in terms of the packing constraint violation. We also discuss some recent applications of our techniques to scheduling problems.

title: Greedy strikes back: improved facility location algorithms
abstract: A fundamental facility location problem is to choose the location of facilities, such as industrial plants and warehouses, to minimize the cost of satisfying the demand for some commodity. There are associated costs for locating the facilities, as well as transportation costs for distributing the commodities. We assume that the transportation costs form a metric. This problem is commonly referred to as theuncapacitated facility locationproblem. Application to bank account location and clustering, as well as many related pieces of work, are discussed by Cornuejols, Nemhauser, and Wolsey. Recently, the first constant factor approximation algorithm for this problem was obtained by Shmoys, Tardos, and Aardal. We show that a simple greedy heuristic combined with the algorithm by Shmoys, Tardos, and Aardal, can be used to obtain an approximation guarantee of 2.408. We discuss a few variants of the problem, demonstrating better approximation factors for restricted versions of the problem. We also show that the problem is max SNP-hard. However, the inapproximability constants derived from the max SNP hardness are very close to one. By relating this problem to Set Cover, we prove a lower bound of 1.463 on the best possible approximation ratio, assumingNP?DTIMEnO(loglogn)].

title: Primal-dual approximation algorithms for metric facility location and k-median problems
abstract: We present approximation algorithms for the metric uncapacitated facility location problem and the metric k-median problem achieving guarantees of 3 and 6 respectively. The distinguishing feature of our algorithms is their low running time: O(m log m) and O(m log m(L+log(n))) respectively, where n and m are the total number of vertices and edges in the underlying graph. The main algorithmic idea is a new extension of the primal-dual schema.

title: Improved combinatorial algorithms for the facility location and k-median problems
abstract: We present improved combinatorial approximation algorithms for the uncapacitated facility location and k-median problems. Two central ideas in most of our results are cost scaling and greedy improvement. We present a simple greedy local search algorithm which achieves an approximation ratio of 2.414+/spl epsiv/ in O/spl tilde/(n/sup 2///spl epsiv/) time. This also yields a bicriteria approximation tradeoff of (1+/spl gamma/, 1+2//spl gamma/) for facility cost versus service cost which is better than previously known tradeoffs and close to the best possible. Combining greedy improvement and cost scaling with a recent primal dual algorithm for facility location due to K. Jain and V. Vazirani (1999), we get an approximation ratio of 1.853 in O/spl tilde/(n/sup 3/) time. This is already very close to the approximation guarantee of the best known algorithm which is LP-based. Further combined with the best known LP-based algorithm for facility location, we get a very slight improvement in the approximation factor for facility location, achieving 1.728. We present improved approximation algorithms for capacitated facility location and a variant. We also present a 4-approximation for the k-median problem, using similar ideas, building on the 6-approximation of Jain and Vazirani. The algorithm runs in O/spl tilde/(n/sup 3/) time.

title: Improved Approximation Algorithms for Metric Facility Location Problems
abstract: In this paper we present a 1.52-approximation algorithm for the uncapacitated metric facility location problem. This algorithm uses an idea of cost scaling, a greedy algorithm of Jain, Mahdian and Saberi, and a greedy augmentation procedure of Charikar, Guha and Khuller. We also present a 2.89-approximation for the capacitated metric facility location problem with soft capacities.

title: An Optimal Bifactor Approximation Algorithm for the Metric Uncapacitated Facility Location Problem
abstract: We obtain a 1.5-approximation algorithm for the metric uncapacitated facility location (UFL) problem, which improves on the previously best known 1.52-approximation algorithm by Mahdian, Ye, and Zhang. Note that the approximability lower bound by Guha and Khuller is $1.463\dots$. An algorithm is a ($\lambda_f$,$\lambda_c$)-approximation algorithm if the solution it produces has total cost at most $\lambda_f\cdot F^*+\lambda_c\cdot C^*$, where $F^*$ and $C^*$ are the facility and the connection cost of an optimal solution. Our new algorithm, which is a modification of the $(1+2/e)$-approximation algorithm of Chudak and Shmoys, is a $(1.6774,1.3738)$-approximation algorithm for the UFL problem and is the first one that touches the approximability limit curve $(\gamma_f,1+2e^{-\gamma_f})$ established by Jain, Mahdian, and Saberi. As a consequence, we obtain the first optimal approximation algorithm for instances dominated by connection costs. When combined with a $(1.11,1.7764)$-approximation algorithm proposed by Jain et al., and later analyzed by Mahdian et al., we obtain the overall approximation guarantee of 1.5 for the metric UFL problem. We also describe how to use our algorithm to improve the approximation ratio for the 3-level version of UFL.

title: A 1.488 approximation algorithm for the uncapacitated facility location problem
abstract: We present a 1.488-approximation algorithm for the metric uncapacitated facility location (UFL) problem. Previously, the best algorithm was due to Byrka (2007). Byrka proposed an algorithm parametrized by @c and used it with @c~1.6774. By either running his algorithm or the algorithm proposed by Jain, Mahdian and Saberi ([email protected]?02), Byrka obtained an algorithm that gives expected approximation ratio 1.5. We show that if @c is randomly selected, the approximation ratio can be improved to 1.488. Our algorithm cuts the gap with the 1.463 approximability lower bound by almost 1/3.

title: Improved Approximation Algorithms for Capacitated Facility Location Problems
abstract: In a recent surprising result, Korupolu, Plaxton, and Rajaraman [10,11] showed that a simple local search heuristic for the capacitated facility location problem (CFLP) in which the service costs obey the triangle inequality produces a solution in polynomial time which is within a factor of 8 + Ɛ of the value of an optimal solution. By simplifying their analysis, we are able to show that the same heuristic produces a solution which is within a factor of 6(1 + Ɛ) of the value of an optimal solution. Our simplified analysis uses the supermodularity of the cost function of the problem and the integrality of the transshipment polyhedron. 
 
Additionally, we consider the variant of the CFLP in which one may open multiple copies of any facility. Using ideas from the analysis of the local search heuristic, we show how to turn any α-approximation algorithm for this variant into one which, at an additional cost of twice the optimum of the standard CFLP, opens at most one additional copy of any facility. This allows us to transform a recent 3-approximation algorithm of Chudak and Shmoys [5] that opens many additional copies of facilities into a polynomial-time algorithm which only opens one additional copy and has cost no more than five times the value of the standard CFLP.

title: Improved approximation algorithms for a capacitated facility location problem
abstract: The study of the location of facilities to serve clients at minimum cost has been one of the most studied themes in the field of Operations Research (see, e.g., the textbook edited by Mirchandani & Francis [S]). We investigate algorithms for a variant of the capacitated fucility location problem, that can be described as follows. There is a set of potential facility locations J= and a set of clients V that require service. Building a facility at location i E 3 has an associated nonnegative fixed cost fi, and each facility installed at this location can service at most u clients. Client j E D must be assigned to one of the open facilities. If a facility at location i E 3 is used to satisfy the demand of client j E D, the service cost incurred is equal to the distance from i to j, cij. The goal is to determine the (integer) number of facilities to install at each potential facility location and an assignment of each client to these facilities so as to minimize the overall total cost, that is, the cost of installing the facilities plus the total service cost. We will only consider the metric variant of the problem in which the distance function c is nonnegative, symmetric and satisfies the triangle inequality. The main result of this paper is a 3-approximation algorithm for the metric capacitated facility location problem, improving on the 5.69-approximation algorithm of [7]. Our work builds on recent results on approximation algorithms for facility location problems that rely on rounding the fractional solution to a linear programming relaxation. Shmoys, Tardos, & Aardal [7] gave the first approximation algorithms with constant performance guarantee for a number of NP-hard metric facility location problems. For the uncapacitated facility location problem (where u = +oo), they gave a

title: A 2-Approximation Algorithm for the Soft-Capacitated Facility Location Problem
abstract: This paper is divided into two parts. In the first part of this paper, we present a 2-approximation algorithm for the soft-capacitated facility location problem. This achieves the integrality gap of the natural LP relaxation of the problem. The algorithm is based on an improved analysis of an algorithm for the linear facility location problem, and a bifactor approximate-reduction from this problem to the soft-capacitated facility location problem. We will define and use the concept of bifactor approximate reductions to improve the approximation factor of several other variants of the facility location problem. In the second part of the paper, we present an alternative analysis of the authors’ 1.52-approximation algorithm for the uncapacitated facility location problem, using a single factor-revealing LP. This answers an open question of [16]Furthermore, this analysis, combined with a recent result of Thorup [21] shows that our algorithm can be implemented in quasi-linear time, achieving the best known approximation factor in the best possible running time.

title: Universal Facility Location
abstract: In the Universal Facility Location problem we are given a set of demand points and a set of facilities. The goal is to assign the demands to facilities in such a way that the sum of service and facility costs is minimized. The service cost is proportional to the distance each unit of demand has to travel to its assigned facility, whereas the facility cost of each facility i depends on the amount of demand assigned to that facility and is given by a cost function f i (·). We present a (7.88 + e)-approximation algorithm for the Universal Facility Location problem based on local search, under the assumption that the cost functions f i are nondecreasing. The algorithm chooses local improvement steps by solving a knapsack-like subproblem using dynamic programming. This is the first constant-factor approximation algorithm for this problem. Our algorithm also slightly improves the best known approximation ratio for the capacitated facility location problem with non-uniform hard capacities.

title: A 5-Approximation for Capacitated Facility Location
abstract: In this paper, we propose and analyze a local search algorithm for the capacitated facility location problem. Our algorithm is a modification of the algorithm proposed by Zhang et al.  and improves the approximation ratio from 5.83 to 5. We achieve this by modifying the close, open and multi operations. The idea of taking linear combinations of inequalities used in Aggarwal et ] is crucial in achieving this result. The example proposed by Zhang et al. also shows that our analysis is tight.

title: LP-based Approximation Algorithms for Capacitated Facility Location
abstract: There has been a great deal of recent work on approximation algorithms for facility location problems [9]. We consider the capacitated facility location problem with hard capacities. We are given a set of facilities, \({\mathcal F}\), and a set of clients \({\mathcal D}\) in a common metric space. Each facility i has a facility opening costf i and capacityu i that specifies the maximum number of clients that may be assigned to this facility. We want to open some facilities from the set \({\mathcal F}\) and assign each client to an open facility so that at most u i clients are assigned to any open facility i. The cost of assigning client j to facility i is given by their distance c ij , and our goal is to minimize the sum of the facility opening costs and the client assignment costs.

title: Bin packing can be solved within 1 + ε in linear time
abstract: For any listL ofn numbers in (0, 1) letL* denote the minimum number of unit capacity bins needed to pack the elements ofL. We prove that, for every positive ε, there exists anO(n)-time algorithmS such that, ifS(L) denotes the number of bins used byS forL, thenS(L)/L*≦1+ε for anyL providedL* is sufficiently large.

title: An efficient approximation scheme for the one-dimensional bin-packing problem
abstract: We present several polynomial-time approximation algorithms for the one-dimensional bin-packing problem. using a subroutine to solve a certain linear programming relaxation of the problem. Our main results are as follows: There is a polynomial-time algorithm A such that A(I) ≤ OPT(I) + O(log2 OPT(I)). There is a polynomial-time algorithm A such that, if m(I) denotes the number of distinct sizes of pieces occurring in instance I, then A(I) ≤ OPT(I) + O(log2 m(I)). There is an approximation scheme which accepts as input an instance I and a positive real number ε, and produces as output a packing using as most (1 + ε) OPT(I) + O(ε-2) bins. Its execution time is O(ε-c n log n), where c is a constant. These are the best asymptotic performance bounds that have been achieved to date for polynomial-time bin-packing. Each of our algorithms makes at most O(log n) calls on the LP relaxation subroutine and takes at most O(n log n) time for other operations. The LP relaxation of bin packing was solved efficiently in practice by Gilmore and Gomory. We prove its membership in P, despite the fact that it has an astronomically large number of variables.

title: Polynomial time approximation schemes for Euclidean TSP and other geometric problems
abstract: We present a polynomial time approximation scheme for Euclidean TSP in /spl Rfr//sup 2/. Given any n nodes in the plane and /spl epsiv/>0, the scheme finds a (1+/spl epsiv/)-approximation to the optimum traveling salesman tour in time n/sup 0(1//spl epsiv/)/. When the nodes are in /spl Rfr//sup d/, the running time increases to n(O/spl tilde/(log/sup d-2/n)//spl epsiv//sup d-1/) The previous best approximation algorithm for the problem (due to Christofides (1976)) achieves a 3/2-approximation in polynomial time. We also give similar approximation schemes for a host of other Euclidean problems, including Steiner Tree, k-TSP, Minimum degree-k, spanning tree, k-MST, etc. (This list may get longer; our techniques are fairly general.) The previous best approximation algorithms for all these problems achieved a constant-factor approximation. All our algorithms also work, with almost no modification, when distance is measured using any geometric norm (such as l/sub p/ for p/spl ges/1 or other Minkowski norms).

title: Approximation schemes for Euclidean k-medians and related problems
abstract: In the k-median problem we are given a set S of n points in a metric space and a positive integer k. We desire to locate k medians in space, such that the sum of the distances from each of the points of S to the nearest median is minimized. This paper gives an approximation scheme for the plane that for any c > 0 produces a solution of cost at most 1+ 1/c times the optimum and runs in time O(n). The approximation scheme also generalizes to some problems related to k-median. Our methodology is to extend Arora’s [1, 2] techniques for the TSP, which hitherto seemed inapplicable to problems such as the k-median problem.