{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,9]],"date-time":"2025-04-09T16:51:56Z","timestamp":1744217516933,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662476710"},{"type":"electronic","value":"9783662476727"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-662-47672-7_10","type":"book-chapter","created":{"date-parts":[[2015,6,19]],"date-time":"2015-06-19T10:07:39Z","timestamp":1434708459000},"page":"116-128","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Approximation Algorithms for Min-Sum k-Clustering and Balanced k-Median"],"prefix":"10.1007","author":[{"given":"Babak","family":"Behsaz","sequence":"first","affiliation":[]},{"given":"Zachary","family":"Friggstad","sequence":"additional","affiliation":[]},{"given":"Mohammad R.","family":"Salavatipour","sequence":"additional","affiliation":[]},{"given":"Rohit","family":"Sivakumar","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,6,20]]},"reference":[{"key":"10_CR1","doi-asserted-by":"crossref","unstructured":"Agarwal, A., Charikar, M., Makarychev, K., Makarychev, Y.: $$O(\\sqrt{\\log n})$$-approximation algorithms for Min UnCut, Min-2CNF deletion, and directed cut problems. In: Proc. of STOC (2005)","DOI":"10.1145\/1060590.1060675"},{"key":"10_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$$-Median and Facility Location Problem. SIAM Journal on Computing 33, 544\u2013562 (2004)","journal-title":"SIAM Journal on Computing"},{"key":"10_CR3","unstructured":"Bartal, Y.: Probabilistic approximation of metric spaces and its algorithmic application. In: Proc. of FOCS (1996)"},{"key":"10_CR4","unstructured":"Bartal, Y., Charikar, M., Raz, D.: Approximating min-sum $$k$$-Clustering in metric spaces. In: Proc. of STOC (2001)"},{"key":"10_CR5","doi-asserted-by":"crossref","unstructured":"Byrka, J., Pensyl, T., Rybicki, B., Srinivasan, A., Trinh, K.: An improved approximation for $$k$$-median, and positive correlation in budgeted optimization. In: Proc. of SODA (2015)","DOI":"10.1137\/1.9781611973730.50"},{"key":"10_CR6","unstructured":"Chuzhoy, J., Rabani, Y.: Approximating k-median with non-uniform capacities. In: Proc. of SODA (2005)"},{"key":"10_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"536","DOI":"10.1007\/978-3-540-70918-3_46","volume-title":"STACS 2007","author":"A Czumaj","year":"2007","unstructured":"Czumaj, A., Sohler, C.: Small space representations for metric min-sum k-clustering and their applications. In: Thomas, W., Weil, P. (eds.) STACS 2007. LNCS, vol. 4393, pp. 536\u2013548. Springer, Heidelberg (2007)"},{"key":"10_CR8","doi-asserted-by":"crossref","unstructured":"Fakcharoenphol, J., Rao, S., Talwar, K.: A tight bound on approximating arbitrary metrics by tree metrics. In: Proc. of STOC (2003)","DOI":"10.1145\/780542.780608"},{"key":"10_CR9","doi-asserted-by":"crossref","unstructured":"de la Vega, W.F., Karpinski, M., Kenyon, C., Rabani, Y.: Approximation schemes for clustering problems. In: Proc. STOC (2003)","DOI":"10.1145\/780542.780550"},{"key":"10_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$$-clustering. Discrete Applied Mathematics 89, 125\u2013142 (1998)","journal-title":"Discrete Applied Mathematics"},{"key":"10_CR11","unstructured":"Indyk, P.: A sublinear time approximation scheme for clustering in metric spaces. In: Proc. of FOCS (1999)"},{"key":"10_CR12","unstructured":"Kann, V., Khanna, S., Lagergren, J., Panconessi, A.: On the hardness of max $$k$$-cut and its dual. In: Israeli Symposium on Theoretical Computer Science (1996)"},{"key":"10_CR13","doi-asserted-by":"crossref","unstructured":"Li, S., Svensson, O.: Approximating $$k$$-median via pseudo-approximation. In: Proc. of STOC (2013)","DOI":"10.1145\/2488608.2488723"},{"issue":"3","key":"10_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$$-Complete Approximation Problems. J. of the ACM (JACM) 23(3), 555\u2013565 (1976)","journal-title":"J. of the ACM (JACM)"},{"key":"10_CR15","doi-asserted-by":"crossref","unstructured":"Schulman, L.J.: Clustering for edge-cost minimization. In: Proc. of STOC (2000)","DOI":"10.1145\/335305.335373"},{"key":"10_CR16","doi-asserted-by":"crossref","unstructured":"Talwar, K.: Bypassing the embedding: algorithms for low dimensional metrics. In: Proc. of STOC (2004)","DOI":"10.1145\/1007352.1007399"},{"key":"10_CR17","unstructured":"Wu, C., Xu, D., Du, D., Wang, Y.: An improved approximation algorithm for $$k$$-median problem using a new factor-revealing LP. http:\/\/arxiv.org\/abs\/1410.4161"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-47672-7_10","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,21]],"date-time":"2023-02-21T02:12:13Z","timestamp":1676945533000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-662-47672-7_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783662476710","9783662476727"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-47672-7_10","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"20 June 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}