APPROXIMATION ALGORITHMS FOR FACILITY LOCATION PROBLEMS

Given a set of facilities F , a set of clientsC, demand dj with each client j, facility opening cost fi for a facility i and cij , the service cost of assigning a client j to facility i, the aim of facility location problem is to open a set of facilities such that the total cost of opening these facilities together with the service cost of all the clients is minimized. The problem addressed in the thesis is a metric facility location problem in which the service costs satisfy the metric property. We discuss the capacitated version of the problem in which a capacity constraint is associated with each facility. Local search based approximation results are presented for three variants of the problem. First is uniform capacitated facility location problem in which all facilities in F have the same capacity, denoted by U . We analyze a local search based heuristic proposed by Kuehn and Hamburger [KH63] to show that this heuristic provides a (3+ )-factor approximation (for the problem) which improves upon the (5.83+ )-factor of Chudak and Williamson [CW99, CW05]. We give an example to show that the analysis is tight. In the second variant different facilities have different capacities and it is called nonuniform capacitated facility location problem or just capacitated facility location problem. For this problem, we give a (5+ )-factor approximation algorithm which improves the current best of (5.83+ ) given by Zhang, Chen and Ye [ZCY05]. For this algorithm also we provide a tight example. The third problem we consider is universal facility location problem which is a generalization of many variants of facility location problem including the first two problems. In this problem facility cost of a facility i ∈ F is given by a function fi(.) and is determined by the capacity allocated at the facility. For this problem, we give a simpler algorithm and show that the cost of the solution is bounded by (5+ ) times the cost of the optimum solution. The result is an improvement upon the (6.702+ )-factor of Vygen [Vyg07] and also upon the (5.83+ )-factor given by Angel, Thang and Regnault [ATR13] in a parallel work. This also implies a simpler algorithm for non-uniform capacitated facility location with the same factor. The key ideas of our analysis are: after assigning the clients of facility being closed to the facility being opened in the operation if the opened facility has some capacity remaining, clients of other facilities in our solution are assigned to it if it results in cost saving; we take a linear combination of some inequalities in a smart way to obtain the claimed approximation guarantees. We also performed some experiments with our third algorithm for a particular case of nonuniform capacitated facility location problem and found that the algorithm works well in practice. The cost of solutions were found to be within (1 + 0.12) times the optimum solution’s cost.