TY - JOUR
T1 - Approximation algorithms for hard capacitated k-facility location problems
AU - Aardal, Karen
AU - van den Berg, Pieter L.
AU - Gijswijt, Dion
AU - Li, Shanfei
PY - 2015
Y1 - 2015
N2 - We study the capacitated k-facility location problem, in which we are given a set of clients with demands, a set of facilities with capacities and a positive integer k. It costs fi to open facility i, and cij for facility i to serve one unit of demand from client j. The objective is to open at most k facilities serving all the demands and satisfying the capacity constraints while minimizing the sum of service and opening costs. In this paper, we give the first fully polynomial time approximation scheme (FPTAS) for the single-sink (single-client) capacitated k-facility location problem. Then, we show that the capacitated k-facility location problem with uniform capacities is solvable in polynomial time if the number of clients is fixed by reducing it to a collection of transportation problems. Third, we analyze the structure of extreme point solutions, and examine the efficiency of this structure in designing approximation algorithms for capacitated k-facility location problems. Finally, we extend our results to obtain an improved approximation algorithm for the capacitated facility location problem with uniform opening costs.
AB - We study the capacitated k-facility location problem, in which we are given a set of clients with demands, a set of facilities with capacities and a positive integer k. It costs fi to open facility i, and cij for facility i to serve one unit of demand from client j. The objective is to open at most k facilities serving all the demands and satisfying the capacity constraints while minimizing the sum of service and opening costs. In this paper, we give the first fully polynomial time approximation scheme (FPTAS) for the single-sink (single-client) capacitated k-facility location problem. Then, we show that the capacitated k-facility location problem with uniform capacities is solvable in polynomial time if the number of clients is fixed by reducing it to a collection of transportation problems. Third, we analyze the structure of extreme point solutions, and examine the efficiency of this structure in designing approximation algorithms for capacitated k-facility location problems. Finally, we extend our results to obtain an improved approximation algorithm for the capacitated facility location problem with uniform opening costs.
U2 - 10.1016/j.ejor.2014.10.011
DO - 10.1016/j.ejor.2014.10.011
M3 - Article
SN - 0377-2217
VL - 242
SP - 358
EP - 368
JO - European Journal of Operational Research
JF - European Journal of Operational Research
IS - 2
ER -