Improved Approximation Algorithms for Facility Location Problems

Abstract

The problem of locating facilities or resources within a specified region is one of the most well researched problems in the field of optimization and operations research. The problem is to identify an optimal set of locations (sites) to open facilities (warehouses) amongst a set of candidate locations, while minimizing the sum of the cost of installing (opening) the facilities plus the cost of allocating (assigning) request nodes (demand nodes) to open facilities. The assignment cost is generally the weighted sum of distances (Euclidean) between request nodes and facilities. Each facility also satisfies minimum or maximum capacity constraints. The most popular variant of facility location problem is the k-median problem. The k-median problem tries to minimize the allocation cost and allows at most k facilities to open or locate. Both FLP and k-median have been used in a wide range of applications including network design, data warehousing, and clustering to name a few. These are NP-hard problems, and have been extensively researched from the perspective of computational complexity i.e. average-case and worst-case performance guarantees. Such problems can be solved by using approximation algorithms. The approximation algorithms obtain a near optimal solution with the help of heuristics and techniques which include local search, linear programming rounding, and primal-dual algorithms. In this thesis, we have developed improved approximation algorithms for different variants of facility location problems. The algorithms we design are mainly based on two approximation techniques: linear programming rounding and the primal-dual approximation. We show that these techniques are very effective in solving variety of location-allocation problems. The major contributions of this thesis to the field of facility location literature are the following:  The Uncapaciated Facility Location Problem with Time Dependent Penalties (UFLPTP): We develop an approximation algorithm for the UFLPTP which we prove xi to be constant factor to the optimal solution. Using a simple linear programming formulation for this problem and subsequently using primal-dual algorithms, we show that the solution to this problem can be obtained within factor 4 approximation. This is the best known upper limit for UFLPTP.  The Uncapacitated Facility Location Problem with Critical Service Time Requirements: We present a Primal-dual based greedy heuristic for this problem. We give first constant factor approximation for such problems with an upper bound of (3 + 𝜖).  The Uncapacitated Facility Location Problem with Parallel Supplies: we design an approximation algorithm using primal-dual approach. The computational complexity of our algorithm is an improvement over the algorithm available in literature, but the performance guarantee is larger. We give a performance guarantee of 6 which is quite larger and can be reduced but at the expense of increased running time.