Geodesic
An approximation algorithm for the hierarchical median problem
Diskretnyj analiz i issledovanie operacij, Tome 15 (2008) no. 4, pp. 84-91

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{DA_2008_15_4_a6,
     author = {V. V. Shenmaier},
     title = {An approximation algorithm for the hierarchical median problem},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {84--91},
     publisher = {mathdoc},
     volume = {15},
     number = {4},
     year = {2008},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2008_15_4_a6/}
}
TY  - JOUR
AU  - V. V. Shenmaier
TI  - An approximation algorithm for the hierarchical median problem
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2008
SP  - 84
EP  - 91
VL  - 15
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2008_15_4_a6/
LA  - ru
ID  - DA_2008_15_4_a6
ER  - 
%0 Journal Article
%A V. V. Shenmaier
%T An approximation algorithm for the hierarchical median problem
%J Diskretnyj analiz i issledovanie operacij
%D 2008
%P 84-91
%V 15
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2008_15_4_a6/
%G ru
%F DA_2008_15_4_a6
V. V. Shenmaier. An approximation algorithm for the hierarchical median problem. Diskretnyj analiz i issledovanie operacij, Tome 15 (2008) no. 4, pp. 84-91. http://geodesic.mathdoc.fr/item/DA_2008_15_4_a6/