Abstract | ||
---|---|---|
In this article, we consider different incremental and hierarchical k-median algorithms with provable performance guarantees and compare their running times and quality of output solutions on different benchmark k-median datasets. We determine that the quality of solutions output by these algorithms for all the datasets is much better than their performance guarantees suggest. Since some of the incremental k-median algorithms require approximate solutions for the k-median problem, we also compare some of the existing k-median algorithms running times and quality of solutions obtained on these datasets. |
Year | DOI | Venue |
---|---|---|
2011 | 10.1145/2543628 | ACM Journal of Experimental Algorithmics |
Keywords | DocType | Volume |
approximate solution,existing k-median algorithm,k-median problem,performance guarantee,provable performance guarantee,hierarchical k-median algorithm,solutions output,output solution,experimental evaluation,different benchmark k-median datasets,incremental k-median algorithm | Conference | 18, |
ISSN | Citations | PageRank |
0302-9743 | 0 | 0.34 |
References | Authors | |
11 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Chandrashekhar Nagarajan | 1 | 151 | 7.62 |
David P. Williamson | 2 | 3564 | 413.34 |