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/

[1] Shenmaier V. V., “Priblizhennyi algoritm dlya odnomernoi zadachi o posledovatelnosti median”, Diskret. analiz i issled. operatsii. Ser. 1, 14:2 (2007), 95–101 | MR

[2] Chrobak M., Kenyon C., Noga J., Young N., “Online medians via online bribery”, Proc. of the 7th Latin american theoretical informatics symposium, Lect. Notes Comp. Sci., 3887, Springer-Verl., Berlin–Heidelberg, 2006, 311–322 | MR

[3] Dasgupta S., “Performance guarantees for hierarchical clustering”, Proc. of the 15th conference on computational learning theory, Springer-Verl., London, 2002, 351–363 | MR | Zbl

[4] Lin G., Nagarajan C., Rajaraman R., Williamson D. P., “A general approach for incremental approximation and hierarchical clustering”, Proc. of the 17th ACM-SIAM symposium on discrete algorithms, ACM Press, New York, 2006, 1147–1156 | MR

[5] Mirchandani P., Francis R. (eds.), Discrete location theory, Wiley and Sons, New York, 1990, 576 pp. | MR | Zbl

[6] Plaxton C. G., “Approximation algorithms for hierarchical location problems”, Proc. of the 35th ACM symposium on theory of computing, ACM Press, New York, 2003, 40–49 | MR