LP-based approximation algorithms for capacitated facility location (Q662296): Difference between revisions

In this paper, the authors describe an LP-based approximation algorithms in the case of the capacitated facility location problem with hard capacities. The novel described approximation algorithms, 5-approximation algorithm, is the first LP-based approximation algorithm for the capacitated facility location problem with hard capacities. The algorithm is obtained for the special case in which all of the facility costs are equal, by rounding the optimal solution to the standard LP relaxation. The main idea was to view the optimal primal solution as a bipartite graph and then this was used to construct a partition of the demand and facilities into clusters: each cluster is centered at a client, and the neighbors of this client contained in the cluster are opened (in the fractional solution) in total at least 1/2.