Abstract:
The hierarchical median problem asks for an hierarchical sequence of solutions of the $k$-median problem for the increasing values of $k$. The best known algorithm for this problem has competitive ratio 20.71. The cases, when all the clients and facilities lie on the path and in Euclidean metric space, are considered. The result is the algorithm with the respective competitive ratio 8 and 8+4$\sqrt2$ (approximately 13.66). Bibl. 6.