{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,22]],"date-time":"2026-01-22T10:26:55Z","timestamp":1769077615610,"version":"3.49.0"},"reference-count":48,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2017,12,14]],"date-time":"2017-12-14T00:00:00Z","timestamp":1513209600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100004663","name":"Ministry of Science and Technology of Taiwan","doi-asserted-by":"crossref","award":["106-2221-E-155-013-"],"award-info":[{"award-number":["106-2221-E-155-013-"]}],"id":[{"id":"10.13039\/501100004663","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2017,12,31]]},"abstract":"<jats:p>\n            Consider the problem of finding a point in a metric space ({ 1,2,\u2026,\n            <jats:italic>n<\/jats:italic>\n            },\n            <jats:italic>d<\/jats:italic>\n            ) with the minimum average distance to other points. We show that this problem has no deterministic\n            <jats:italic>o<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\n              1+1\/(\n              <jats:italic>h<\/jats:italic>\n              -1)\n            <\/jats:sup>\n            \/\n            <jats:italic>h<\/jats:italic>\n            )-query 2\n            <jats:italic>h<\/jats:italic>\n            \u00b7 (1-\u03f5))-approximation algorithms for any constant \u03f5 &gt;0 and any\n            <jats:italic>h<\/jats:italic>\n            =\n            <jats:italic>h<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            )\u2208 Z\n            <jats:sup>+<\/jats:sup>\n            \\ {1} satisfying\n            <jats:italic>h<\/jats:italic>\n            =\n            <jats:italic>o<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\n              1\/(\n              <jats:italic>h<\/jats:italic>\n              -1)\n            <\/jats:sup>\n            ). Combining our result with existing ones, we determine the best approximation ratio achievable by deterministic\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>1+\u03f5<\/jats:sup>\n            )-query (respectively,\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>1+\u03f5<\/jats:sup>\n            )-time) algorithms to be 2\u2308 1\/\u03f5 \u2309, for\n            <jats:italic>all<\/jats:italic>\n            constants \u03f5 \u2208 (0,1).\n          <\/jats:p>","DOI":"10.1145\/3154858","type":"journal-article","created":{"date-parts":[[2017,12,15]],"date-time":"2017-12-15T13:39:24Z","timestamp":1513345164000},"page":"1-23","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Metric 1-Median Selection"],"prefix":"10.1145","volume":"9","author":[{"given":"Ching-Lueh","family":"Chang","sequence":"first","affiliation":[{"name":"Department of Computer Science and Engineering, Yuan Ze University, Taoyuan, Taiwan"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2017,12,14]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804090"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICPP.2006.57"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2450142.2450144"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1121\/1.1906679"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(02)00102-5"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1080\/0022250X.2001.9990249"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.socnet.2007.11.001"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218127407018403"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01592245"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623403424740"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/11427186_24"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1651274.1651282"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2011.12.003"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2013.02.003"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2015.07.058"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2016.08.004"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICASI.2017.7988144"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2002.1882"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780548"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746562"},{"key":"e_1_2_1_21_1","unstructured":"Shiri Chechik Edith Cohen and Haim Kaplan. 2015. Average distance queries through weighted samples in graphs and metric spaces: High scalability with tight statistical guarantees. In Proceedings of the 18th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems and the 19th International Workshop on Randomization and Computation (APPROX-RANDOM\u201915). 659--679.  Shiri Chechik Edith Cohen and Haim Kaplan. 2015. Average distance queries through weighted samples in graphs and metric spaces: High scalability with tight statistical guarantees. In Proceedings of the 18th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems and the 19th International Workshop on Randomization and Computation (APPROX-RANDOM\u201915). 659--679."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/070699007"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/1873601.1873626"},{"key":"e_1_2_1_24_1","unstructured":"Thomas H. Cormen Charles E. Leiserson Ronald L. Rivest and Clifford Stein. 2009. Introduction to Algorithms (3rd ed.). The MIT Press.   Thomas H. Cormen Charles E. Leiserson Ronald L. Rivest and Clifford Stein. 2009. Introduction to Algorithms (3rd ed.). The MIT Press."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/1192035.1192049"},{"key":"e_1_2_1_26_1","doi-asserted-by":"crossref","unstructured":"Artur Czumaj and Christian Sohler. 2010. Sublinear-time algorithms. In Property Testing O. Goldreich (Ed.). Springer-Verlag Berlin Heidelberg 41--64.   Artur Czumaj and Christian Sohler. 2010. Sublinear-time algorithms. In Property Testing O. Goldreich (Ed.). Springer-Verlag Berlin Heidelberg 41--64.","DOI":"10.1007\/978-3-642-16367-8_5"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1734213.1734219"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00081"},{"key":"e_1_2_1_29_1","first-page":"97","article-title":"The art of uninformed decisions: A primer to property testing","volume":"75","author":"Fischer Eldar","year":"2001","journal-title":"Bull. Eur. Assoc. Theoret. Comput. Sci."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/0378-8733(78)90021-7"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.v32:4"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2003.1198387"},{"key":"e_1_2_1_33_1","volume-title":"Data Stream Management: Processing High-Speed Data Streams","author":"Guha Sudipto"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/301250.301366"},{"key":"e_1_2_1_35_1","unstructured":"Piotr Indyk. 2000. High-Dimensional Computational Geometry. Ph.D. Dissertation. Stanford University.  Piotr Indyk. 2000. High-Dimensional Computational Geometry. Ph.D. Dissertation. Stanford University."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.510012"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/375827.375845"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-004-0182-6"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02090400"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/1667053.1667054"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1023\/B:MACH.0000033114.18632.e0"},{"key":"e_1_2_1_42_1","first-page":"2","article-title":"Hardness results for the center and median string problems under the weighted and unweighted edit distances","volume":"3","author":"Nicolas Fran\u00e7ois","year":"2005","journal-title":"J. Discrete Algor."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1137\/100791075"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02289527"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1137\/120888703"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1137\/0211027"},{"key":"e_1_2_1_47_1","doi-asserted-by":"crossref","unstructured":"Stanley Wasserman and Katherine Faust. 1994. Social Network Analysis: Methods and Applications. Cambridge University Press.  Stanley Wasserman and Katherine Faust. 1994. Social Network Analysis: Methods and Applications. Cambridge University Press.","DOI":"10.1017\/CBO9780511815478"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2013.12.004"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3154858","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3154858","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:26:38Z","timestamp":1750213598000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3154858"}},"subtitle":["Query Complexity vs. Approximation Ratio"],"short-title":[],"issued":{"date-parts":[[2017,12,14]]},"references-count":48,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2017,12,31]]}},"alternative-id":["10.1145\/3154858"],"URL":"https:\/\/doi.org\/10.1145\/3154858","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"value":"1942-3454","type":"print"},{"value":"1942-3462","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,12,14]]},"assertion":[{"value":"2016-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-12-14","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}