Volume 15, No 4, 2008, P. 84-91

UDC 519.176
V. V. Shenmaier
An approximation algorithm for the hierarchical median problem

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.

Keywords: $k$-median problem, hierarchical clustering, incremental median problem, approximation algorithm, competitive ratio.

Shenmaier Vladimir Vladimirovich ¹
1. S. L. Sobolev Institute of Mathematics, SB RAS,
4 Acad. Koptyug Ave., 630090 Novosibirsk, Russia
e-mail: shenmaier@mail.ru