{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T03:20:14Z","timestamp":1761621614476,"version":"3.37.3"},"reference-count":16,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2022,2,8]],"date-time":"2022-02-08T00:00:00Z","timestamp":1644278400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,2,8]],"date-time":"2022-02-08T00:00:00Z","timestamp":1644278400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100008982","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1566137","1750780"],"award-info":[{"award-number":["1566137","1750780"]}],"id":[{"id":"10.13039\/501100008982","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2022,5]]},"DOI":"10.1007\/s00453-022-00940-0","type":"journal-article","created":{"date-parts":[[2022,2,8]],"date-time":"2022-02-08T09:06:40Z","timestamp":1644311200000},"page":"1441-1465","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Metric Violation Distance: Hardness and Approximation"],"prefix":"10.1007","volume":"84","author":[{"given":"Chenglin","family":"Fan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6584-4843","authenticated-orcid":false,"given":"Benjamin","family":"Raichel","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gregory Van","family":"Buskirk","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,2,8]]},"reference":[{"key":"940_CR1","doi-asserted-by":"crossref","unstructured":"Abraham, I., Bartal, Y., Chan, T.-H., Dhamdhere, K., Gupta, A., Kleinberg, J., Neiman, O., Slivkins, A.: Metric embeddings with relaxed guarantees. In: 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 83\u2013100 (2005)","DOI":"10.1109\/SFCS.2005.51"},{"issue":"1","key":"940_CR2","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1137\/060653391","volume":"30","author":"J Brickell","year":"2008","unstructured":"Brickell, J., Dhillon, I., Sra, S., Tropp, J.: The metric nearness problem. SIAM J. Matrix Anal. Appl. 30(1), 375\u2013396 (2008)","journal-title":"SIAM J. Matrix Anal. Appl."},{"issue":"1\u20132","key":"940_CR3","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1007\/BF02776078","volume":"52","author":"J Bourgain","year":"1985","unstructured":"Bourgain, J.: On Lipschitz embedding of finite metric spaces in Hilbert space. Israel J. Math. 52(1\u20132), 46\u201352 (1985)","journal-title":"Israel J. Math."},{"issue":"6","key":"940_CR4","doi-asserted-by":"publisher","first-page":"2303","DOI":"10.1137\/060670511","volume":"38","author":"T-H Chan","year":"2009","unstructured":"Chan, T.-H., Dhamdhere, K., Gupta, A., Kleinberg, J., Slivkins, A.: Metric embeddings with relaxed guarantees. SIAM J. Comput. 38(6), 2303\u20132329 (2009)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"940_CR5","doi-asserted-by":"publisher","first-page":"432","DOI":"10.1006\/jcss.2001.1785","volume":"63","author":"F Chung","year":"2001","unstructured":"Chung, F., Garrett, M., Graham, R., Shallcross, D.: Distance realization problems with applications to internet tomography. J. Comput. Syst. Sci. 63(3), 432\u2013448 (2001)","journal-title":"J. Comput. Syst. Sci."},{"key":"940_CR6","unstructured":"Christofides, N.: Worst-case analysis of a new heuristic for the travelling salesman problem. Technical Report 388, Graduate School of Industrial Administration, Carnegie Mellon University (1976)"},{"issue":"6","key":"940_CR7","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1145\/2184319.2184343","volume":"55","author":"E Cand\u00e8s","year":"2012","unstructured":"Cand\u00e8s, E., Recht, B.: Exact matrix completion via convex optimization. Commun. ACM 55(6), 111\u2013119 (2012)","journal-title":"Commun. ACM"},{"key":"940_CR8","unstructured":"Fan, C., Gilbert, A., Raichel, B., Sonthalia, R., Van Buskirk, G.: Generalized metric repair on graphs. In: 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT), volume 162 of LIPIcs, pp. 25:1\u201325:22 (2020)"},{"key":"940_CR9","doi-asserted-by":"crossref","unstructured":"Fan, C., Raichel, B., Gregory Van Buskirk. Metric violation distance: Hardness and approximation. In: Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 196\u2013209 (2018)","DOI":"10.1137\/1.9781611975031.14"},{"key":"940_CR10","doi-asserted-by":"crossref","unstructured":"Gilbert, A., Jain, L.: If it ain\u2019t broke, don\u2019t fix it: Sparse metric repair. In: 55th Annual Allerton Conference on Communication, Control, and Computing, pp. 612\u2013619 (2017)","DOI":"10.1109\/ALLERTON.2017.8262793"},{"key":"940_CR11","doi-asserted-by":"crossref","unstructured":"Indyk, P., Matou\u0161ek, J.: Low-distortion embeddings of finite metric spaces. In: Handbook of Discrete and Computational Geometry, pp. 177\u2013196. CRC Press (2004)","DOI":"10.1201\/9781420035315.ch8"},{"issue":"3","key":"940_CR12","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1016\/j.jcss.2007.06.019","volume":"74","author":"S Khot","year":"2008","unstructured":"Khot, S., Regev, O.: Vertex cover might be hard to approximate to within 2-epsilon. J. Comput. Syst. Sci. 74(3), 335\u2013349 (2008)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"940_CR13","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1007\/BF01200757","volume":"15","author":"N Linial","year":"1995","unstructured":"Linial, N., London, E., Rabinovich, Y.: The geometry of graphs and some of its algorithmic applications. Combinatorica 15(2), 215\u2013245 (1995)","journal-title":"Combinatorica"},{"key":"940_CR14","unstructured":"Matou\u0161ek, J.: Lecture Notes on Metric Embeddings (2013). http:\/\/kam.mff.cuni.cz\/~matousek\/ba-a4.pdf"},{"issue":"3","key":"940_CR15","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. ACM 23(3), 555\u2013565 (1976)","journal-title":"J. ACM"},{"key":"940_CR16","doi-asserted-by":"crossref","unstructured":"Sidiropoulos, A., Wang, D., Wang, Y.: Metric embeddings with outliers. In: Proceedings of Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 670\u2013689 (2017)","DOI":"10.1137\/1.9781611974782.43"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-00940-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-022-00940-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-00940-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,18]],"date-time":"2024-09-18T02:39:11Z","timestamp":1726627151000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-022-00940-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,2,8]]},"references-count":16,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2022,5]]}},"alternative-id":["940"],"URL":"https:\/\/doi.org\/10.1007\/s00453-022-00940-0","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2022,2,8]]},"assertion":[{"value":"4 February 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 January 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 February 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}