{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T05:58:53Z","timestamp":1725861533355},"publisher-location":"Cham","reference-count":13,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319426334"},{"type":"electronic","value":"9783319426341"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-319-42634-1_11","type":"book-chapter","created":{"date-parts":[[2016,7,19]],"date-time":"2016-07-19T11:50:21Z","timestamp":1468929021000},"page":"131-142","source":"Crossref","is-referenced-by-count":1,"title":["Metric 1-Median Selection: Query Complexity vs. Approximation Ratio"],"prefix":"10.1007","author":[{"given":"Ching-Lueh","family":"Chang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,7,20]]},"reference":[{"issue":"3","key":"11_CR1","doi-asserted-by":"crossref","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 problems. SIAM J. Comput. 33(3), 544\u2013562 (2004)","journal-title":"SIAM J. Comput."},{"key":"11_CR2","unstructured":"Chang, C.-L.: A deterministic sublinear-time nonadaptive algorithm for metric $$1$$ -median selection. To appear in Theoretical Computer Science"},{"key":"11_CR3","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.tcs.2011.12.003","volume":"426","author":"C-L Chang","year":"2012","unstructured":"Chang, C.-L.: Some results on approximate $$1$$ -median selection in metric spaces. Theor. Comput. Sci. 426, 1\u201312 (2012)","journal-title":"Theor. Comput. Sci."},{"issue":"8","key":"11_CR4","doi-asserted-by":"crossref","first-page":"288","DOI":"10.1016\/j.ipl.2013.02.003","volume":"113","author":"C-L Chang","year":"2013","unstructured":"Chang, C.-L.: Deterministic sublinear-time approximations for metric $$1$$ -median selection. Inf. Process. Lett. 113(8), 288\u2013292 (2013)","journal-title":"Inf. Process. Lett."},{"key":"11_CR5","unstructured":"Chang, C.-L.: A lower bound for metric $$1$$ -median selection. Technical report. arXiv:1401.2195 (2014)"},{"issue":"3","key":"11_CR6","doi-asserted-by":"crossref","first-page":"923","DOI":"10.1137\/070699007","volume":"39","author":"K Chen","year":"2009","unstructured":"Chen, K.: On coresets for $$k$$ -median and $$k$$ -means clustering in metric and Euclidean spaces and their applications. SIAM J. Comput. 39(3), 923\u2013947 (2009)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"11_CR7","doi-asserted-by":"crossref","first-page":"515","DOI":"10.1109\/TKDE.2003.1198387","volume":"15","author":"S Guha","year":"2003","unstructured":"Guha, S., Meyerson, A., Mishra, N., Motwani, R., O\u2019Callaghan, L.: Clustering data streams: theory and practice. IEEE Trans. Knowl. Data Eng. 15(3), 515\u2013528 (2003)","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"11_CR8","doi-asserted-by":"crossref","unstructured":"Indyk, P.: Sublinear time algorithms for metric space problems. In: Proceedings of the 31st Annual ACM Symposium on Theory of Computing, pp. 428\u2013434 (1999)","DOI":"10.1145\/301250.301366"},{"key":"11_CR9","unstructured":"Indyk, P.: High-Dimensional Computational Geometry. Ph.D. thesis, Stanford University (2000)"},{"key":"11_CR10","doi-asserted-by":"crossref","unstructured":"Jaiswal, R., Kumar, A., Sen, S.: A simple $${D}^2$$ -sampling based PTAS for $$k$$ -means and other clustering problems. In: Proceedings of the 18th Annual International Conference on Computing and Combinatorics, pp. 13\u201324 (2012)","DOI":"10.1007\/978-3-642-32241-9_2"},{"issue":"2","key":"11_CR11","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1145\/1667053.1667054","volume":"57","author":"A Kumar","year":"2010","unstructured":"Kumar, A., Sabharwal, Y., Sen, S.: Linear-time approximation schemes for clustering problems in any dimensions. J. ACM 57(2), 5 (2010)","journal-title":"J. ACM"},{"issue":"1\u20133","key":"11_CR12","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1023\/B:MACH.0000033114.18632.e0","volume":"56","author":"RR Mettu","year":"2004","unstructured":"Mettu, R.R., Plaxton, C.G.: Optimal time bounds for approximate clustering. Mach. Learn. 56(1\u20133), 35\u201360 (2004)","journal-title":"Mach. Learn."},{"issue":"4","key":"11_CR13","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1016\/j.ipl.2013.12.004","volume":"114","author":"B-Y Wu","year":"2014","unstructured":"Wu, B.-Y.: On approximating metric $$1$$ -median in sublinear time. Inf. Process. Lett. 114(4), 163\u2013166 (2014)","journal-title":"Inf. Process. Lett."}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-42634-1_11","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,6,24]],"date-time":"2017-06-24T14:44:11Z","timestamp":1498315451000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-42634-1_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319426334","9783319426341"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-42634-1_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]}}}