{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,16]],"date-time":"2026-04-16T10:17:52Z","timestamp":1776334672395,"version":"3.51.2"},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642366932","type":"print"},{"value":"9783642366949","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-36694-9_25","type":"book-chapter","created":{"date-parts":[[2013,3,11]],"date-time":"2013-03-11T10:08:39Z","timestamp":1362996519000},"page":"290-301","source":"Crossref","is-referenced-by-count":6,"title":["The Euclidean k-Supplier Problem"],"prefix":"10.1007","author":[{"given":"Viswanath","family":"Nagarajan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Baruch","family":"Schieber","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hadas","family":"Shachnai","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"25_CR1","doi-asserted-by":"crossref","unstructured":"Arora, S.: Nearly linear time approximation schemes for Euclidean TSP and other geometric problems. In: FOCS, pp. 554\u2013563 (1997)","DOI":"10.1007\/3-540-63248-4_5"},{"issue":"6","key":"25_CR2","doi-asserted-by":"publisher","first-page":"891","DOI":"10.1145\/293347.293348","volume":"45","author":"S. Arya","year":"1998","unstructured":"Arya, S., Mount, D.M., Netanyahu, N.S., Silverman, R., Wu, A.Y.: An optimal algorithm for approximate nearest neighbor searching in fixed dimensions. J. ACM\u00a045(6), 891\u2013923 (1998)","journal-title":"J. ACM"},{"issue":"3","key":"25_CR3","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1007\/PL00009390","volume":"20","author":"T.M. Chan","year":"1998","unstructured":"Chan, T.M.: Approximate nearest neighbor queries revisited. Discrete & Computational Geometry\u00a020(3), 359\u2013373 (1998)","journal-title":"Discrete & Computational Geometry"},{"key":"25_CR4","doi-asserted-by":"crossref","unstructured":"Clarkson, K.L.: An algorithm for approximate closest-point queries. In: Symposium on Computational Geometry, SoCG, pp. 160\u2013164 (1994)","DOI":"10.1145\/177424.177609"},{"key":"25_CR5","doi-asserted-by":"crossref","unstructured":"Feder, T., Greene, D.H.: Optimal algorithms for approximate clustering. In: STOC, pp. 434\u2013444 (1988)","DOI":"10.1145\/62212.62255"},{"key":"25_CR6","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1016\/0304-3975(85)90224-5","volume":"38","author":"T.F. Gonzalez","year":"1985","unstructured":"Gonzalez, T.F.: Clustering to minimize the maximum intercluster distance. Theor. Comput. Sci.\u00a038, 293\u2013306 (1985)","journal-title":"Theor. Comput. Sci."},{"key":"25_CR7","doi-asserted-by":"crossref","unstructured":"Har-Peled, S., Mazumdar, S.: On coresets for k-means and k-median clustering. In: STOC, pp. 291\u2013300 (2004)","DOI":"10.1145\/1007352.1007400"},{"issue":"2","key":"25_CR8","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1287\/moor.10.2.180","volume":"10","author":"D.S. Hochbaum","year":"1985","unstructured":"Hochbaum, D.S., Shmoys, D.B.: A best possible heuristic for the k-center problem. Mathematics of Operations Research\u00a010(2), 180\u2013184 (1985)","journal-title":"Mathematics of Operations Research"},{"issue":"3","key":"25_CR9","doi-asserted-by":"publisher","first-page":"533","DOI":"10.1145\/5925.5933","volume":"33","author":"D.S. Hochbaum","year":"1986","unstructured":"Hochbaum, D.S., Shmoys, D.B.: A unified approach to approximation algorithms for bottleneck problems. J. ACM\u00a033(3), 533\u2013550 (1986)","journal-title":"J. ACM"},{"issue":"3","key":"25_CR10","doi-asserted-by":"publisher","first-page":"757","DOI":"10.1137\/S0097539702404055","volume":"37","author":"S.G. Kolliopoulos","year":"2007","unstructured":"Kolliopoulos, S.G., Rao, S.: A nearly linear-time approximation scheme for the Euclidean k-median problem. SIAM J. Comput.\u00a037(3), 757\u2013782 (2007)","journal-title":"SIAM J. Comput."},{"key":"25_CR11","doi-asserted-by":"crossref","unstructured":"Micali, S., Vazirani, V.V.: An \n                  \n                    \n                  \n                  $O(\\sqrt{V} E)$\n                 Algorithm for Finding Maximum Matching in General Graphs. In: FOCS, pp. 17\u201327 (1980)","DOI":"10.1109\/SFCS.1980.12"},{"issue":"1","key":"25_CR12","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/s00453-005-1187-5","volume":"45","author":"M. Mucha","year":"2006","unstructured":"Mucha, M., Sankowski, P.: Maximum matchings in planar graphs via gaussian elimination. Algorithmica\u00a045(1), 3\u201320 (2006)","journal-title":"Algorithmica"},{"key":"25_CR13","volume-title":"Combinatorial optimization","author":"A. Schrijver","year":"2003","unstructured":"Schrijver, A.: Combinatorial optimization. Springer, New York (2003)"},{"issue":"4","key":"25_CR14","doi-asserted-by":"publisher","first-page":"569","DOI":"10.1007\/BF01553909","volume":"4","author":"P.M. Vaidya","year":"1989","unstructured":"Vaidya, P.M.: Approximate minimum weight matching on points in k-dimensional space. Algorithmica\u00a04(4), 569\u2013583 (1989)","journal-title":"Algorithmica"},{"issue":"6","key":"25_CR15","doi-asserted-by":"publisher","first-page":"1201","DOI":"10.1137\/0218080","volume":"18","author":"P.M. Vaidya","year":"1989","unstructured":"Vaidya, P.M.: Geometry helps in matching. SIAM J. Comput.\u00a018(6), 1201\u20131225 (1989)","journal-title":"SIAM J. Comput."}],"container-title":["Lecture Notes in Computer Science","Integer Programming and Combinatorial Optimization"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-36694-9_25","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,11]],"date-time":"2019-05-11T17:33:06Z","timestamp":1557595986000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-36694-9_25"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642366932","9783642366949"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-36694-9_25","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013]]}}}