The facility location problem with general cost functions

From MaRDI portal





Given a finite set of clients and a finite set of possible facility sites, the concave facility location problem considered in this paper is to find an assignment of all clients to facility sites such that the sum of connection costs and facility costs is minimized. It is assumed that the connection costs are symmetric and satisfy the triangle inequality, and that the facility costs are given by concave functions of the number of clients assigned to the respective facility. It is first noted that the concave facility location problem can be reduced to the capacitated facility location problem for which a 1.52-approximation algorithm with a time complexity of \(O(n^6)\) was given by \textit{M. Mahdian, Y. Ye} and \textit{J. Zhang} [Lect. Notes Comput. sci. 2462, 229-242 (2002; Zbl 1013.90115)] and \textit{M. Mahdian, E. Markakis, A. Saberi} and \textit{V. Vazirani} [Lect. Notes Comput. Sci. 2129, 127-137 (200; Zbl 0998.68701)]. Then a greedy-type 1.861-approximation algorithm with an improved running time of at most \(O(n^3 \log n)\) is presented. The algorithm can be viewed as a natural generalization of an earlier algorithm by Mahdian, Markakis, Saberi and Vazirani (2001). This also extends to the derivation of the approximation factor of 1.861 which uses techniques of dual-fitting and factor-revealing LPs.




Cited in
(34)








This page was built for publication: The facility location problem with general cost functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4422623)