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.