{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,7]],"date-time":"2026-06-07T08:49:20Z","timestamp":1780822160654,"version":"3.54.1"},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540671411","type":"print"},{"value":"9783540465416","type":"electronic"}],"license":[{"start":{"date-parts":[[2000,1,1]],"date-time":"2000-01-01T00:00:00Z","timestamp":946684800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1007\/3-540-46541-3_31","type":"book-chapter","created":{"date-parts":[[2007,8,2]],"date-time":"2007-08-02T12:03:24Z","timestamp":1186056204000},"page":"370-381","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":12,"title":["The Hardness of Approximating Spanner Problems"],"prefix":"10.1007","author":[{"given":"Michael","family":"Elkin","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"David","family":"Peleg","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2000,3,24]]},"reference":[{"key":"31_CR1","series-title":"Lect. Notes in Comput. Sci.","doi-asserted-by":"crossref","first-page":"26","DOI":"10.1007\/3-540-52846-6_75","volume-title":"Proc. 2nd Scandinavian Workshop on Algorithm Theory","author":"I. Alth\u00f6fer","year":"1990","unstructured":"I. Alth\u00f6fer, G. Das, D. Dobkin and D. Joseph, Generating sparse spanners for weighted graphs, Proc. 2nd Scandinavian Workshop on Algorithm Theory, Lect. Notes in Comput. Sci., Vol. 447, pp. 26\u201337, Springer-Verlag, New York\/Berlin, 1990."},{"key":"31_CR2","unstructured":"Baruch Awerbuch, Alan Baratz, and David Peleg. Efficient broadcast and lightweight spanners. Unpublished manuscript, November 1991."},{"key":"31_CR3","doi-asserted-by":"crossref","unstructured":"B. Bollobas, Extremal Graph Theory. Academic Press, 1978.","DOI":"10.1007\/978-1-4612-9967-7"},{"key":"31_CR4","unstructured":"L. Cai, Tree-2-Spanners, Technical Report 91-4, Simon Fraser University, 1991."},{"key":"31_CR5","unstructured":"R. D. Carr, S. Doddi, G. Konjevod, M. V. Marathe On the Red-Blue Set Cover Problem, Los Alamos National Laboratory."},{"key":"31_CR6","unstructured":"P. Chanas, Dimensionnement de r\u00e9seaux ATM, PhD thesis, CNET Sophia, Sept. 1998."},{"key":"31_CR7","doi-asserted-by":"crossref","unstructured":"B. Chandra, G. Das, G. Narasimhan and J. Soares, New Sparseness Results on Graph Spanners, Proc 8th ACM Symposium on Computational Geometry, pages 192\u2013201, 1992.","DOI":"10.1145\/142675.142717"},{"key":"31_CR8","doi-asserted-by":"crossref","unstructured":"L.P. Chew, There is a planar graph almost as good as the complete graph, Proc. ACM Symp. on Computational Geometry, 1986, pp. 169\u2013177","DOI":"10.1145\/10515.10534"},{"key":"31_CR9","series-title":"Lect. Notes in Comput. Sci.","doi-asserted-by":"crossref","first-page":"168","DOI":"10.1007\/3-540-51859-2_15","volume-title":"Proc. Int. Symp. on Optimal Algorithms","author":"G. Das","year":"1989","unstructured":"G. Das and D. Joseph, Which triangulation approximates the complete graphs, Proc. Int. Symp. on Optimal Algorithms, Lect. Notes in Comput. Sci., Vol. 401, pp. 168\u2013192, Springer-Verlag, New York\/Berlin, 1989"},{"key":"31_CR10","unstructured":"I. Dinur and S. Safra, On the hardness of Approximating Label Cover, Electronic Colloquium on Computational Complexity, Report No. 15 (1999)"},{"key":"31_CR11","doi-asserted-by":"crossref","unstructured":"D.P. Dobkin, S.J. Friedman and K.J. Supowit, Delaunay graphs are almost as good as complete graphs, Proc. 31st IEEE Symp. on Foundations of Computer Science, 1987, pp. 20\u201326.","DOI":"10.1109\/SFCS.1987.18"},{"key":"31_CR12","doi-asserted-by":"crossref","unstructured":"Y. Dodis and S. Khanna, Designing Networks with Bounded Pairwise Distance, Proc. 30th ACM Ann. Symp. of Theory of Computing, 1999.","DOI":"10.1145\/301250.301447"},{"key":"31_CR13","unstructured":"M.-L. Elkin and D. Peleg, The Hardness of Approximating Spanner Problems, Technical Report MCS99-14, the Weizmann Institute of Science, 1999."},{"key":"31_CR14","unstructured":"M.-L. Elkin and D. Peleg, The Client-Server 2-Spanner Problem and Applications to Network Design, Technical Report MCS99-24, the Weizmann Institute of Science, 1999."},{"key":"31_CR15","unstructured":"M.-L. Elkin and D. Peleg, Classification of Spanner Problems, in preparation."},{"key":"31_CR16","unstructured":"M.-L. Elkin and D. Peleg, Strong Inapproximability of the Basic k-Spanner Problem, Technical Report MCS99-23, the Weizmann Institute of Science, 1999."},{"key":"31_CR17","doi-asserted-by":"crossref","unstructured":"U. Feige and L. Lovasz, Two prover one-round proof systems: Their power and their problems, Proc. 24th ACM Symp. on Theory of Computing, 733\u2013741, 1992","DOI":"10.1145\/129712.129783"},{"key":"31_CR18","volume-title":"Approximation Algorithms for NP-hard Problems","author":"D. Hochbaum","year":"1997","unstructured":"D. Hochbaum Approximation Algorithms for NP-hard Problems, PWS Publishing Company, Boston, 1997."},{"key":"31_CR19","series-title":"Lect. Notes in Comput. Sci.","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1007\/BFb0053970","volume-title":"Proc. APPROX.","author":"G. Kortsarz","year":"1998","unstructured":"G. Kortsarz, On the Hardness of Approximating Spanners, Proc. APPROX., Lect. Notes in Comput. Sci., Vol. 1444, pp. 135\u2013146, Springer-Verlag, New York\/Berlin, 1998."},{"key":"31_CR20","doi-asserted-by":"publisher","first-page":"222","DOI":"10.1006\/jagm.1994.1032","volume":"17","author":"G. Kortsarz","year":"1994","unstructured":"G. Kortsarz and D. Peleg, Generating Sparse 2-Spanners. J. Algorithms, 17 (1994) 222\u2013236.","journal-title":"J. Algorithms"},{"key":"31_CR21","series-title":"Lect. Notes in Comput. Sci.","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1007\/3-540-51859-2_2","volume-title":"Proc. Int. Symp. on Optimal Algorithms","author":"C. Levcopoulos","year":"1989","unstructured":"C. Levcopoulos and A. Lingas, There are planar graphs almost as good as the complete graphs and as short as minimum spanning trees, Proc. Int. Symp. on Optimal Algorithms, Lect. Notes in Comput. Sci., Vol. 401, pp. 9\u201313, Springer-Verlag, New York\/Berlin, 1989"},{"key":"31_CR22","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1002\/net.3230230206","volume":"23","author":"A.L. Liestman","year":"1993","unstructured":"A.L. Liestman and T. Shermer, Grid Spanners, Networks\n                        23 (1993), 123\u2013133.","journal-title":"Networks"},{"key":"31_CR23","unstructured":"D. Peleg, Locality-Sensitive Distributed Computing, unpublished manuscript, 1999."},{"key":"31_CR24","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1002\/jgt.3190130114","volume":"13","author":"D. Peleg","year":"1989","unstructured":"D. Peleg and A. Sch\u00e4ffer, Graph Spanners, J. Graph Theory\n                        13 (1989), 99\u2013116.","journal-title":"J. Graph Theory"},{"key":"31_CR25","doi-asserted-by":"publisher","first-page":"740","DOI":"10.1137\/0218050","volume":"18","author":"D. Peleg","year":"1989","unstructured":"D. Peleg and J.D. Ullman, An optimal synchronizer for the hypercube, SIAM J. Computing\n                        18 (1989), pp. 740\u2013747.","journal-title":"SIAM J. Computing"},{"key":"31_CR26","unstructured":"H. Regev, The weight of the Greedy Graph Spanner, Technical Report CS95-22, July 1995."}],"container-title":["Lecture Notes in Computer Science","STACS 2000"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-46541-3_31","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,19]],"date-time":"2019-05-19T09:48:46Z","timestamp":1558259326000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-46541-3_31"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540671411","9783540465416"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/3-540-46541-3_31","relation":{},"ISSN":["0302-9743"],"issn-type":[{"value":"0302-9743","type":"print"}],"subject":[],"published":{"date-parts":[[2000]]},"assertion":[{"value":"24 March 2000","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}