An approximation algorithm for the hierarchical median problem

The hierarchical median problem asks for a hierarchical sequence of solutions to the k-median problems of growing cardinality. The best algorithm known for this problem in the general metric case has competitive ratio 20.71. In the paper, the case is under study that the clients and facilities lie on the real line, as well as the case of a Euclidean space. An algorithm is proposed with competitive ratio 8 in the case of the real line, and 8 + 4√2 (approximately 13.66), in the Euclidean case.