Approximation algorithms for facility location problems (extended abstract)

By David B. Shmoys, É. Tardos, Karen I. Aardal. 1997

We present new approximation algorithms for several facility location problems. In each facility location problem that we study, there is a set of locations at which we may build a facility (such as a warehouse), where the cost of building at location i is fi; furthermore, there is a set 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. The objective is to determine a set of locations at which to open facilities so as to minimize the total facility and assignment costs. In the uncapacitated case, each facility can service an unlimited number of clients, whereas in the capacitated case, each facility can serve, for example, at most u clients. These models and a number of closely related ones have been studied extensively in the Operations Research literature. We shall consider the case in which the assignment costs are symmetric and satisfy the triangle inequality. For the uncapacitated facility location, we give a polynomial-time algorithm that (cid:12)nds a solution within a factor of 3.16 of the optimal. This is the (cid:12)rst constant performance guarantee known for this problem. We also present approximation algorithms with constant performance guarantees for a number of capacitated models as well as a generalization in which there is a 2-level hierarchy of facilities. Our results are based on the (cid:12)ltering and rounding technique of Lin & Vitter. We also give a randomized variant of this technique that can then be derandomized to yield improved performance guarantees.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Proportionally Fair Clustering (2019, background): “sic context for clustering work (Gonzalez, 1985; Shmoys et al., 1997; Charikar et al., 2002; Arya et al., 2004), and is perhaps best known as the setting for the celebrated k-means heuristic (independently discovered many times, see (Jain, 2010) for a brief history).”
On the placement of Web server replicas (2001, background): “[28] developed the first approximation algorithms with constant performance guarantee for a number of metric facility location problems.”
Optimal Time Bounds for Approximate Clustering (2002, background): “It is wellknown that thek-median problem isNP-hard; furthermore, it is known to beNP-hard to achieve an approximation ratio better than1 + 1e [7].”
Minimizing Energies with Hierarchical Costs (2012, background): “Generalizing Facility Location In the optimization and operations research communities, uncapacitated facility location (UFL) is a well-studied problem (e.g. Shmoys et al. 1998).”
Stochastic Optimization for Natural Disaster Asset Prepositioning (2010, background): “…facilities for ﬁre stations or ambulances under the paradigm of set covering problems: a demand is covered if there exists at least one available unit within a speciﬁed distance from its location (see, e.g., Cabot et al. 1970, Church and ReVelle 1974, Shmoys et al. 1997, Tonegas et al. 1971).”
A 1.488 approximation algorithm for the uncapacitated facility location problem (2011, methodology): “Shmoys, Tardos, and Aardal [12] used the techniques of Lin and Vitter [10] to give the first constant-approximation algorithm.”
Fast Approximate Energy Minimization with Label Costs (2010, background): “Hochbaum [12] later showed that greedy yields a O(log |P|)-approximation in general, and better bounds exist for special cost functions (see [23] for review).”