{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:20:48Z","timestamp":1750306848409,"version":"3.41.0"},"reference-count":13,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2013,11,28]],"date-time":"2013-11-28T00:00:00Z","timestamp":1385596800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2013,12]]},"abstract":"<jats:p>\n            In this article, we consider different incremental and hierarchical\n            <jats:italic>k<\/jats:italic>\n            -median algorithms with provable performance guarantees and compare their running times and quality of output solutions on different benchmark\n            <jats:italic>k<\/jats:italic>\n            -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\n            <jats:italic>k<\/jats:italic>\n            -median algorithms require approximate solutions for the\n            <jats:italic>k<\/jats:italic>\n            -median problem, we also compare some of the existing\n            <jats:italic>k<\/jats:italic>\n            -median algorithms running times and quality of solutions obtained on these datasets.\n          <\/jats:p>","DOI":"10.1145\/2543628","type":"journal-article","created":{"date-parts":[[2014,9,2]],"date-time":"2014-09-02T14:18:04Z","timestamp":1409667484000},"source":"Crossref","is-referenced-by-count":0,"title":["An Experimental Evaluation of Incremental and Hierarchical\n            <i>k<\/i>\n            -Median Algorithms"],"prefix":"10.1145","volume":"18","author":[{"given":"Chandrashekhar","family":"Nagarajan","sequence":"first","affiliation":[{"name":"Facebook"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David P.","family":"Williamson","sequence":"additional","affiliation":[{"name":"Cornell University"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2013,11,28]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1026130003508"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702416402"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(85)90040-2"},{"volume-title":"Proceedings of the 31th Annual ACM Symposium on Theory of Computing, 1-10","author":"Charikar M.","key":"e_1_2_1_4_1","unstructured":"M. Charikar , S. Guha , E. Tardos , and D. B. Shmoys . 1999. A constant-factor approximation algorithm for the k-median problem (extended abstract) . In Proceedings of the 31th Annual ACM Symposium on Theory of Computing, 1-10 . M. Charikar, S. Guha, E. Tardos, and D. B. Shmoys. 1999. A constant-factor approximation algorithm for the k-median problem (extended abstract). In Proceedings of the 31th Annual ACM Symposium on Theory of Computing, 1-10."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/3118772.3119146"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(94)00159-6"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/950620.950621"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/375827.375845"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/0137041"},{"volume-title":"Proceedings of the 45th Annual ACM Symposium on Theory of Computing, 901-910","author":"Li S.","key":"e_1_2_1_10_1","unstructured":"S. Li and O. Svensson . 2013. Approximating k-median via pseudo-approximation . In Proceedings of the 45th Annual ACM Symposium on Theory of Computing, 901-910 . S. Li and O. Svensson. 2013. Approximating k-median via pseudo-approximation. In Proceedings of the 45th Annual ACM Symposium on Theory of Computing, 901-910."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/070698257"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/639069.773507"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2005.09.004"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2543628","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2543628","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:10:15Z","timestamp":1750234215000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2543628"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,11,28]]},"references-count":13,"alternative-id":["10.1145\/2543628"],"URL":"https:\/\/doi.org\/10.1145\/2543628","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"type":"print","value":"1084-6654"},{"type":"electronic","value":"1084-6654"}],"subject":[],"published":{"date-parts":[[2013,11,28]]}}}