An approximation algorithm for the Euclidean incremental median problem |
| |
Institution: | Sobolev Institute of Mathematics, Novosibirsk, Russia |
| |
Abstract: | In the incremental version of the -median problem, we find a sequence of facility sets , where each contains at most facilities. This sequence is said to be -competitive if the cost of each is at most times the optimum cost of facilities. The best deterministic (randomized) algorithm available for the metric space has a competitive ratio of (). The best one for the one-dimensional problem finds a -competitive sequence. We give a -competitive solution for the high-dimensional Euclidean space. |
| |
Keywords: | Incremental medians Euclidean medians Hierarchical clustering Approximation algorithm Online algorithm |
本文献已被 ScienceDirect 等数据库收录! |