×

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).

MSC:

90B80 Discrete location and assignment
90C10 Integer programming

Citations:

Zbl 1138.90417