The \(k\)-centrum multi-facility location problem (Q5931794)

The author introduced the \(k\)-centrum \(p\)-facility location problem, which is a generalisation of both \(p\)-center and \(p\)-median problems. In this problem, it is necessary to find \(p\) points in a graph minimizing the sum of \(k\) farthest nodes from the set of these points. Then the author suggested polynomial time algorithms to solve \(k\)-centrum 1-facility location problems on path graph and tree graph and performed out algorithm complexity investigation. At the end of the first part of the paper, it is shown, how to extend the general approximation algorithms of \textit{Y. Bartal} [Proc. 30th Anneal Symposium on Theory of Computing, 161-168 (1998)] and \textit{M. Charikar, C. Chekuri, A. Goel} and \textit{S. Guha} [same Proc., 114-123 (1998)] to solve the \(k\)-centrum single facility problem on a general graph. The second part of the study was focused on working out the algorithms, which are able to solve the general \(k\)-centrum \(p\)-facility location problem on path and tree graphs, respectively. Both algorithms are based on a dynamic programming approach and there was proved that their time complexity is also polynomial.