{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,31]],"date-time":"2022-03-31T00:10:25Z","timestamp":1648685425042},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2010,9,1]],"date-time":"2010-09-01T00:00:00Z","timestamp":1283299200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[2010,9]]},"DOI":"10.1007\/s00493-010-2302-z","type":"journal-article","created":{"date-parts":[[2011,3,25]],"date-time":"2011-03-25T21:24:05Z","timestamp":1301088245000},"page":"581-615","source":"Crossref","is-referenced-by-count":2,"title":["Maximum gradient embeddings and monotone clustering"],"prefix":"10.1007","volume":"30","author":[{"given":"Manor","family":"Mendel","sequence":"first","affiliation":[]},{"given":"Assaf","family":"Naor","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2011,3,13]]},"reference":[{"issue":"1","key":"2302_CR1","doi-asserted-by":"crossref","first-page":"78","DOI":"10.1137\/S0097539792224474","volume":"24","author":"N. Alon","year":"1995","unstructured":"N. Alon, R. Karp, D. Peleg and D. West: A graph-theoretic game and its application to the k-server problem, SIAM J. Comput. 24(1) (1995), 78\u2013100.","journal-title":"SIAM J. Comput."},{"issue":"3","key":"2302_CR2","doi-asserted-by":"crossref","first-page":"544","DOI":"10.1137\/S0097539702416402","volume":"33","author":"V. Arya","year":"2004","unstructured":"V. Arya, N. Garg, R. Khandekar, A. Meyerson, K. Munagala and V. Pandit: Local search heuristics for k-median and facility location problems, SIAM J. Comput. 33(3) (2004), 544\u2013562.","journal-title":"SIAM J. Comput."},{"key":"2302_CR3","first-page":"184","volume-title":"37th Annual Symposium on Foundations of Computer Science","author":"Y. Bartal","year":"1996","unstructured":"Y. Bartal: Probabilistic approximation of metric spaces and its algorithmic applications, in: 37th Annual Symposium on Foundations of Computer Science, (1996), pp. 184\u2013193, IEEE Comput. Soc. Press, Los Alamitos, CA."},{"key":"2302_CR4","first-page":"161","volume-title":"Proceedings of the 30th Annual ACM Symposium on Theory of Computing","author":"Y. Bartal","year":"1998","unstructured":"Y. Bartal: On approximating arbitrary metrics by tree metrics, in: Proceedings of the 30th Annual ACM Symposium on Theory of Computing, (1998), pp. 161\u2013168, ACM, New York."},{"key":"2302_CR5","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1145\/380752.380754","volume-title":"Proceedings of the 33rd Annual ACM Symposium on Theory of Computing","author":"Y. Bartal","year":"2001","unstructured":"Y. Bartal, Yair, M. Charikar and D. Raz: Approximating min-sum k-clustering in metric spaces, in: Proceedings of the 33rd Annual ACM Symposium on Theory of Computing, (2001), pp. 11\u201320, ACM, New York."},{"issue":"2","key":"2302_CR6","doi-asserted-by":"crossref","first-page":"643","DOI":"10.4007\/annals.2005.162.643","volume":"162","author":"Y. Bartal","year":"2005","unstructured":"Y. Bartal, N. Linial, M. Mendel and A. Naor: On metric Ramsey-type phenomena, Ann. of Math. (2) 162(2) (2005), 643\u2013709.","journal-title":"Ann. of Math. (2)"},{"issue":"1","key":"2302_CR7","doi-asserted-by":"crossref","first-page":"248","DOI":"10.1137\/S0097539703433122","volume":"34","author":"Y. Bartal","year":"2004","unstructured":"Y. Bartal and M. Mendel: Multi-embedding of metric spaces, SIAM J. Comput. 34(1) (2004), 248\u2013259.","journal-title":"SIAM J. Comput."},{"key":"2302_CR8","doi-asserted-by":"crossref","unstructured":"S. G. Bobkov and Ch. Houdr\u00e9: Some connections between isoperimetric and Sobolev-type inequalities, Mem. Amer. Math. Soc. 129(616) (1997), viii+111.","DOI":"10.1090\/memo\/0616"},{"key":"2302_CR9","series-title":"Grundlehren der Mathematischen Wissenschaften","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-12494-9","volume-title":"Metric spaces of non-positive curvature","author":"M. R. Bridson","year":"1999","unstructured":"M. R. Bridson and A, Haefliger: Metric spaces of non-positive curvature, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], 319, Springer-Verlag, Berlin, (1999), xxii+643 pp."},{"issue":"5","key":"2302_CR10","doi-asserted-by":"crossref","first-page":"766","DOI":"10.1145\/1089023.1089026","volume":"52","author":"B. Brinkman","year":"2005","unstructured":"B. Brinkman and M. Charikar: On the impossibility of dimension reduction in l 1, J. ACM 52(5) (2005), 766\u2013788.","journal-title":"J. ACM"},{"issue":"2","key":"2302_CR11","doi-asserted-by":"crossref","first-page":"358","DOI":"10.1137\/S0097539701395978","volume":"34","author":"G. Calinescu","year":"2004","unstructured":"G. Calinescu, H. Karloff and Y. Rabani: Approximation algorithms for the 0-extension problem, SIAM J. Comput. 34(2) (2004\/05), 358\u2013372.","journal-title":"SIAM J. Comput."},{"issue":"4","key":"2302_CR12","doi-asserted-by":"crossref","first-page":"803","DOI":"10.1137\/S0097539701398594","volume":"34","author":"M. Charikar","year":"2005","unstructured":"M. Charikar and S. Guha: Improved combinatorial algorithms for facility location problems, SIAM J. Comput. 34(4) (2005), 803\u2013824.","journal-title":"SIAM J. Comput."},{"issue":"1","key":"2302_CR13","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1006\/jcss.2002.1882","volume":"65","author":"M. Charikar","year":"2002","unstructured":"M. Charikar, S. Guha, \u00c9. Tardos and D. B. Shmoys: A constant-factor approximation algorithm for the k-median problem, J. Comput. System Sci. 65(1) (2002), 129\u2013149.","journal-title":"J. Comput. System Sci."},{"issue":"2","key":"2302_CR14","doi-asserted-by":"crossref","first-page":"417","DOI":"10.1016\/j.jcss.2003.07.014","volume":"68","author":"M. Charikar","year":"2004","unstructured":"M. Charikar and R. Panigrahy: Clustering to minimize the sum of cluster diameters, J. Comput. Syst. Sci. 68(2) (2004), 417\u2013441.","journal-title":"J. Comput. Syst. Sci."},{"key":"2302_CR15","first-page":"119","volume-title":"Discrete location theory; Wiley-Intersci. Ser. Discrete Math. Optim.","author":"G. Cornu\u00e9jols","year":"1990","unstructured":"G. Cornu\u00e9jols, G. L. Nemhauser and L. A. Wolsey: The uncapacitated facility location problem, in: Discrete location theory; Wiley-Intersci. Ser. Discrete Math. Optim., (1990), pp. 119\u2013171, Wiley, New York."},{"key":"2302_CR16","first-page":"494","volume-title":"Proceedings of the 37th Annual ACM Symposium on Theory of Computing","author":"M. Elkin","year":"2005","unstructured":"M. Elkin, Y. Emek, D. A. Spielman and S.-H. Teng: Lower-stretch spanning trees, in: Proceedings of the 37th Annual ACM Symposium on Theory of Computing, (2005), pp. 494\u2013503, ACM, New York."},{"key":"2302_CR17","unstructured":"J. Fakcharoenphol, S. Rao and K. Talwar: A tight bound on approximating arbitrary metrics by tree metrics, in: Proceedings of the 35th annual ACM Symposium on Theory of Computing, (2003), pp. 448\u2013455."},{"key":"2302_CR18","unstructured":"M. Gromov: Metric structures for Riemannian and non-Riemannian spaces, Progress in Mathematics 152, Based on the 1981 French original; With appendices by M. Katz, P. Pansu and S. Semmes. Translated from the French by Sean Michael Bates, Birkh\u00e4user Boston Inc., Boston, MA, (1999), xx+585 pp."},{"key":"2302_CR19","first-page":"649","volume-title":"Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, San Francisco, CA, 1998","author":"S. Guha","year":"1998","unstructured":"S. Guha and S. Khuller: Greedy strikes back: improved facility location algorithms, in: Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, San Francisco, CA, 1998; (1998), pp. 649\u2013657, ACM, New York."},{"key":"2302_CR20","doi-asserted-by":"crossref","first-page":"970","DOI":"10.1145\/1109557.1109665","volume-title":"Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, Miami, FL, 2006","author":"A. Gupta","year":"2006","unstructured":"A. Gupta, M.T. Hajiaghayi and H. R\u00e4cke: Oblivious Network Design, in: Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, Miami, FL, 2006; (2006), pp. 970\u2013979, ACM, New York."},{"issue":"2","key":"2302_CR21","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1007\/s00493-004-0015-x","volume":"24","author":"A. Gupta","year":"2004","unstructured":"A. Gupta, I. Newman, Y. Rabinovich and A. Sinclair: Cuts, trees and l 1-embeddings of graphs; Combinatorica 24(2) (2004), 233\u2013269.","journal-title":"Combinatorica"},{"issue":"5","key":"2302_CR22","doi-asserted-by":"crossref","first-page":"1148","DOI":"10.1137\/S0097539704446281","volume":"35","author":"S. Har-Peled","year":"2006","unstructured":"S. Har-Peled and M. Mendel: Fast construction of nets in low dimensional metrics, and their applications; SIAM J. Comput. 35(5) (2006), 1148\u20131184.","journal-title":"SIAM J. Comput."},{"issue":"6","key":"2302_CR23","doi-asserted-by":"crossref","first-page":"795","DOI":"10.1145\/950620.950621","volume":"50","author":"K. Jain","year":"2003","unstructured":"K. Jain, M. Mahdian, E. Markakis, A. Saberi and V. V. Vazirani: Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP, J. ACM 50(6) (2003), 795\u2013824.","journal-title":"J. ACM"},{"issue":"2","key":"2302_CR24","doi-asserted-by":"crossref","first-page":"274","DOI":"10.1145\/375827.375845","volume":"48","author":"K. Jain","year":"2001","unstructured":"K. Jain and V. V. Vazirani: Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and Lagrangian relaxation, J. ACM 48(2) (2001), 274\u2013296.","journal-title":"J. ACM"},{"issue":"3","key":"2302_CR25","doi-asserted-by":"crossref","first-page":"433","DOI":"10.1007\/s00453-003-1070-1","volume":"38","author":"K. Jain","year":"2004","unstructured":"K. Jain and V. V. Vazirani: An approximation algorithm for the fault tolerant metric facility location problem, Algorithmica (Approximation algorithms) 38(3) (2004), 433\u2013439.","journal-title":"Algorithmica (Approximation algorithms)"},{"issue":"1","key":"2302_CR26","doi-asserted-by":"crossref","first-page":"146","DOI":"10.1006\/jagm.2000.1100","volume":"37","author":"M. R. Korupolu","year":"2000","unstructured":"M. R. Korupolu, C. G. Plaxton and R. Rajaraman: Analysis of a local search heuristic for facility location problems, J. Algorithms 37(1) (2000), 146\u2013188.","journal-title":"J. Algorithms"},{"issue":"4","key":"2302_CR27","doi-asserted-by":"crossref","first-page":"839","DOI":"10.1007\/s00039-005-0527-6","volume":"15","author":"R. Krauthgamer","year":"2005","unstructured":"R. Krauthgamer, J. R. Lee, M. Mendel and A. Naor: Measured descent: A new embedding method for finite metrics, Geom. Funct. Anal. 15(4) (2005), 839\u2013858.","journal-title":"Geom. Funct. Anal."},{"key":"2302_CR28","series-title":"Mathematical Surveys and Monographs","volume-title":"The concentration of measure phenomenon","author":"M. Ledoux","year":"2001","unstructured":"M. Ledoux: The concentration of measure phenomenon, Mathematical Surveys and Monographs 89, American Mathematical Society, Providence, RI, (2001), x+181 pp."},{"issue":"4","key":"2302_CR29","first-page":"745","volume":"14","author":"J. R. Lee","year":"2004","unstructured":"J. R. Lee and A. Naor: Embedding the diamond graph in L p and dimension reduction in L 1, Geom. Funct. Anal. 14(4) (2004), 745\u2013747.","journal-title":"Geom. Funct. Anal."},{"issue":"1","key":"2302_CR30","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1007\/s00222-004-0400-5","volume":"160","author":"J. R. Lee","year":"2005","unstructured":"J. R. Lee and A. Naor: Extending Lipschitz functions via random metric partitions, Invent. Math. 160(1) (2005), 59\u201395.","journal-title":"Invent. Math."},{"issue":"2","key":"2302_CR31","doi-asserted-by":"crossref","first-page":"451","DOI":"10.1016\/j.aim.2003.12.001","volume":"189","author":"M. Mendel","year":"2004","unstructured":"M. Mendel and A. Naor: Euclidean quotients of finite metric spaces, Adv. Math. 189(2) (2004), 451\u2013494.","journal-title":"Adv. Math."},{"issue":"2","key":"2302_CR32","doi-asserted-by":"crossref","first-page":"253","DOI":"10.4171\/JEMS\/79","volume":"9","author":"M. Mendel","year":"2007","unstructured":"M. Mendel and A. Naor: Ramsey partitions and proximity data structures, J. European Math. Soc. 9(2) (2007), 253\u2013275.","journal-title":"J. European Math. Soc."},{"key":"2302_CR33","series-title":"Wiley-Interscience Series in Discrete Mathematics and Optimization","volume-title":"Discrete location theory","author":"P. B. Mirchandani","year":"1990","unstructured":"P. B. Mirchandani and R. L. Francis: Discrete location theory, Wiley-Interscience Series in Discrete Mathematics and Optimization, JohnWiley & Sons Inc., New York, (1990), xvi+555 pp."},{"issue":"1","key":"2302_CR34","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1007\/s00454-002-2813-5","volume":"29","author":"I. Newman","year":"2003","unstructured":"I. Newman and Y. Rabinovich: A lower bound on the distortion of embedding planar metrics into Euclidean space, Discrete Comput. Geom. 29(1) (2003), 77\u201381.","journal-title":"Discrete Comput. Geom."},{"issue":"1","key":"2302_CR35","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1007\/PL00009336","volume":"19","author":"Y. Rabinovich","year":"1998","unstructured":"Y. Rabinovich and R. Raz: Lower bounds on the distortion of embedding finite metric spaces in graphs, Discrete Comput. Geom. 19(1) (1998), 79\u201394.","journal-title":"Discrete Comput. Geom."},{"key":"2302_CR36","unstructured":"D. B. Shmoys, \u00c9. Tardos and K. Aardal: Approximation algorithms for facility location problems (extended abstract), in: Proceedings of the 29th annual ACM Symposium on Theory of Computing, (1997), pp. 265\u2013274."},{"key":"2302_CR37","first-page":"735","volume-title":"Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Ch. Swamy","year":"2003","unstructured":"Ch. Swamy and D. B. Shmoys: Fault-tolerant facility location, in: Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, ACM, New York, (2003), pp. 735\u2013736."}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-010-2302-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00493-010-2302-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-010-2302-z","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,11,20]],"date-time":"2021-11-20T18:51:39Z","timestamp":1637434299000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00493-010-2302-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,9]]},"references-count":37,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2010,9]]}},"alternative-id":["2302"],"URL":"https:\/\/doi.org\/10.1007\/s00493-010-2302-z","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"value":"0209-9683","type":"print"},{"value":"1439-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,9]]}}}