{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,20]],"date-time":"2026-03-20T11:54:27Z","timestamp":1774007667869,"version":"3.50.1"},"reference-count":16,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2018,5,15]],"date-time":"2018-05-15T00:00:00Z","timestamp":1526342400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100000038","name":"NSERC","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2019,3]]},"DOI":"10.1007\/s00453-018-0454-1","type":"journal-article","created":{"date-parts":[[2018,5,15]],"date-time":"2018-05-15T12:23:56Z","timestamp":1526387036000},"page":"1006-1030","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["Approximation Algorithms for Min-Sum k-Clustering and Balanced k-Median"],"prefix":"10.1007","volume":"81","author":[{"given":"Babak","family":"Behsaz","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zachary","family":"Friggstad","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7650-2045","authenticated-orcid":false,"given":"Mohammad R.","family":"Salavatipour","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rohit","family":"Sivakumar","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,5,15]]},"reference":[{"key":"454_CR1","doi-asserted-by":"crossref","unstructured":"Agarwal, A., Charikar, M., Makarychev, K., Makarychev, Y.: $$O(\\sqrt{\\log n})$$ O ( log n ) -approximation algorithms for Min UnCut, Min-2CNF Deletion, and directed cut problems. In: Proceedings of STOC (2005)","DOI":"10.1145\/1060590.1060675"},{"key":"454_CR2","doi-asserted-by":"publisher","first-page":"544","DOI":"10.1137\/S0097539702416402","volume":"33","author":"V Arya","year":"2004","unstructured":"Arya, V., Garg, N., Khandekar, R., Meyerson, A., Munagala, K., Pandit, V.: Local search heuristics for $$k$$ k -median and facility location problem. SIAM J. Comput. 33, 544\u2013562 (2004)","journal-title":"SIAM J. Comput."},{"key":"454_CR3","unstructured":"Bartal, Y.: Probabilistic approximation of metric spaces and its algorithmic application. In: Proceedings of FOCS (1996)"},{"key":"454_CR4","doi-asserted-by":"crossref","unstructured":"Bartal, Y., Charikar, M., Raz, D.: Approximating min-sum $$k$$ k -clustering in metric spaces. In: Proceedings of STOC (2001)","DOI":"10.1145\/380752.380754"},{"key":"454_CR5","doi-asserted-by":"crossref","unstructured":"Byrka, J., Pensyl, T., Rybicki, B., Srinivasan, A., Trinh, K.: An improved approximation for $$k$$ k -median, and positive correlation in budgeted optimization. In: Proceedings of SODA (2015)","DOI":"10.1137\/1.9781611973730.50"},{"key":"454_CR6","unstructured":"Chuzhoy, J., Rabani, Y.: Approximating k-median with non-uniform capacities In: Proceedings of SODA (2005)"},{"key":"454_CR7","unstructured":"Czumaj, A., Sohler, C.: Small space representations for metric min-sum $$k$$ k -clustering and their applications. In: Proceedings of STACS (2007)"},{"key":"454_CR8","doi-asserted-by":"crossref","unstructured":"Fakcharoenphol, J., Rao, S., Talwar, K.: A tight bound on approximating arbitrary metrics by tree metrics. In: Proceedings of STOC (2003)","DOI":"10.1145\/780542.780608"},{"key":"454_CR9","doi-asserted-by":"crossref","unstructured":"Fernandez de la Vega, W., Karpinski, M., Kenyon, C., Rabani, Y.: Approximation schemes for clustering problems. In Proceedings of STOC (2003)","DOI":"10.1145\/780542.780550"},{"key":"454_CR10","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1016\/S0166-218X(98)00100-0","volume":"89","author":"N Guttman-Beck","year":"1998","unstructured":"Guttman-Beck, N., Hassin, R.: Approximation algorithms for min-sum $$p$$ p -clustering. Discrete Appl. Math. 89, 125\u2013142 (1998)","journal-title":"Discrete Appl. Math."},{"key":"454_CR11","unstructured":"Indyk, P.: A sublinear time approximation scheme for clustering in metric spaces. In: Proceedings of FOCS (1999)"},{"key":"454_CR12","unstructured":"Kann, V., Khanna, S., Lagergren, J., Panconessi, A.: On the hardness of max $$k$$ k -cut and its dual. In: Israeli Symposium on Theoretical Computer Science (1996)"},{"key":"454_CR13","doi-asserted-by":"crossref","unstructured":"Li, S., Svensson, O.: Approximating $$k$$ k -median via pseudo-approximation. In: Proceedings of STOC (2013)","DOI":"10.1145\/2488608.2488723"},{"issue":"3","key":"454_CR14","doi-asserted-by":"publisher","first-page":"555","DOI":"10.1145\/321958.321975","volume":"23","author":"S Sahni","year":"1976","unstructured":"Sahni, S., Gonzalez, T.: $$P$$ P -complete approximation problems. J. ACM (JACM) 23(3), 555\u2013565 (1976)","journal-title":"J. ACM (JACM)"},{"key":"454_CR15","doi-asserted-by":"crossref","unstructured":"Schulman, L.J.: Clustering for edge-cost minimization. In: Proceedings of STOC (2000)","DOI":"10.1145\/335305.335373"},{"key":"454_CR16","doi-asserted-by":"crossref","unstructured":"Talwar, K.: Bypassing the embedding: algorithms for low dimensional metrics. In: Proceedings of STOC (2004)","DOI":"10.1145\/1007352.1007399"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-018-0454-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-018-0454-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-018-0454-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,2]],"date-time":"2023-09-02T17:00:44Z","timestamp":1693674044000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-018-0454-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,5,15]]},"references-count":16,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2019,3]]}},"alternative-id":["454"],"URL":"https:\/\/doi.org\/10.1007\/s00453-018-0454-1","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,5,15]]},"assertion":[{"value":"10 July 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 May 2018","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 May 2018","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}