An integer programming formulation of capacitated facility location problem. (English) Zbl 1472.90049
Summary: We study the three approximation algorithms developed for solving Uncapacitated Facility Location Problem (UCFLP). These are: the algorithms based on linear programming rounding, the primal-dual algorithm of K. Jain and V. V. Vazirani [J. ACM 48, No. 2, 274–296 (2001; Zbl 1138.90417)], and the algorithms based on dual-fitting. They give the reader an insight into the main approach to solve the Facility Location Problem (FLP).