{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T19:15:39Z","timestamp":1725563739083},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642157745"},{"type":"electronic","value":"9783642157752"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-15775-2_7","type":"book-chapter","created":{"date-parts":[[2010,9,1]],"date-time":"2010-09-01T10:47:32Z","timestamp":1283338052000},"page":"72-83","source":"Crossref","is-referenced-by-count":1,"title":["Fast Approximation in Subspaces by Doubling Metric Decomposition"],"prefix":"10.1007","author":[{"given":"Marek","family":"Cygan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lukasz","family":"Kowalik","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marcin","family":"Mucha","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marcin","family":"Pilipczuk","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Piotr","family":"Sankowski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"7_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1007\/10719839_9","volume-title":"LATIN 2000: Theoretical Informatics","author":"M.A. Bender","year":"2000","unstructured":"Bender, M.A., Farach-Colton, M.: The LCA problem revisited. In: Gonnet, G.H., Viola, A. (eds.) LATIN 2000. LNCS, vol.\u00a01776, pp. 88\u201394. Springer, Heidelberg (2000)"},{"key":"7_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"258","DOI":"10.1007\/978-3-540-69903-3_24","volume-title":"Algorithm Theory \u2013 SWAT 2008","author":"D. Bil\u00f2","year":"2008","unstructured":"Bil\u00f2, D., B\u00f6ckenhauer, H.-J., Hromkovi\u010d, J., Kr\u00e1lovi\u010d, R., M\u00f6mke, T., Widmayer, P., Zych, A.: Reoptimization of steiner trees. In: Gudmundsson, J. (ed.) SWAT 2008. LNCS, vol.\u00a05124, pp. 258\u2013269. Springer, Heidelberg (2008)"},{"issue":"36","key":"7_CR3","doi-asserted-by":"publisher","first-page":"3428","DOI":"10.1016\/j.tcs.2008.04.039","volume":"410","author":"H.-J. B\u00f6ckenhauer","year":"2009","unstructured":"B\u00f6ckenhauer, H.-J., Hromkovi\u010d, J., Kr\u00e1lovi\u010d, R., M\u00f6mke, T., Rossmanith, P.: Reoptimization of steiner trees: Changing the terminal set. Theor. Comput. Sci.\u00a0410(36), 3428\u20133435 (2009)","journal-title":"Theor. Comput. Sci."},{"key":"7_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"50","DOI":"10.1007\/978-3-540-77566-9_5","volume-title":"SOFSEM 2008: Theory and Practice of Computer Science","author":"H.-J. B\u00f6ckenhauer","year":"2008","unstructured":"B\u00f6ckenhauer, H.-J., Hromkovi\u010d, J., M\u00f6mke, T., Widmayer, P.: On the hardness of reoptimization. In: Geffert, V., Karhum\u00e4ki, J., Bertoni, A., Preneel, B., N\u00e1vrat, P., Bielikov\u00e1, M. (eds.) SOFSEM 2008. LNCS, vol.\u00a04910, pp. 50\u201365. Springer, Heidelberg (2008)"},{"key":"7_CR5","unstructured":"Chan, H.T.-H., Gupta, A., Maggs, B.M., Zhou, S.: On hierarchical routing in doubling metrics. In: Proc. SODA 2005, pp. 762\u2013771 (2005)"},{"issue":"1","key":"7_CR6","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1007\/PL00009449","volume":"22","author":"K.L. Clarkson","year":"1999","unstructured":"Clarkson, K.L.: Nearest neighbor queries in metric spaces. Discrete & Computational Geometry\u00a022(1), 63\u201393 (1999)","journal-title":"Discrete & Computational Geometry"},{"key":"7_CR7","unstructured":"Cole, R., Hariharan, R., Lewenstein, M., Porat, E.: A faster implementation of the Goemans-Williamson clustering algorithm. In: Proc. SODA 2001, pp. 17\u201325 (2001)"},{"issue":"2","key":"7_CR8","first-page":"86","volume":"4","author":"B. Escoffier","year":"2009","unstructured":"Escoffier, B., Milanic, M., Paschos, V.T.: Simple and fast reoptimizations for the Steiner tree problem. Algorithmic Operations Research\u00a04(2), 86\u201394 (2009)","journal-title":"Algorithmic Operations Research"},{"key":"7_CR9","doi-asserted-by":"crossref","unstructured":"Har-Peled, S., Mendel, M.: Fast construction of nets in low dimensional metrics, and their applications. In: Proc. SCG 2005, pp. 150\u2013158 (2005)","DOI":"10.1145\/1064092.1064117"},{"key":"7_CR10","doi-asserted-by":"crossref","unstructured":"Jia, L., Lin, G., Noubir, G., Rajaraman, R., Sundaram, R.: Universal aproximations for TSP, Steiner Tree and Set Cover. In: STOC 2005, pp. 1234\u20135415 (2005)","DOI":"10.1145\/1060590.1060649"},{"key":"7_CR11","unstructured":"Krauthgamer, R., Lee, J.R.: Navigating nets: simple algorithms for proximity search. In: Proc. SODA 2004, pp. 798\u2013807 (2004)"},{"issue":"2","key":"7_CR12","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1137\/S0097539703435716","volume":"36","author":"M. Mahdian","year":"2006","unstructured":"Mahdian, M., Ye, Y., Zhang, J.: Approximation algorithms for metric facility location problems. SIAM Journal on Computing\u00a036(2), 411\u2013432 (2006)","journal-title":"SIAM Journal on Computing"},{"key":"7_CR13","doi-asserted-by":"crossref","unstructured":"Salama, H.F., Reeves, D.S., Viniotis, Y., Sheu, T.-L.: Evaluation of multicast routing algorithms for real-time communication on high-speed networks. In: Proceedings of the IFIP Sixth International Conference on High Performance Networking VI, pp. 27\u201342 (1995)","DOI":"10.1007\/978-0-387-34949-7_3"},{"key":"7_CR14","unstructured":"Thorup, M.: Quick and good facility location. In: Proc. SODA 2003, pp. 178\u2013185 (2003)"},{"issue":"2","key":"7_CR15","doi-asserted-by":"publisher","first-page":"405","DOI":"10.1137\/S0097539701388884","volume":"34","author":"M. Thorup","year":"2005","unstructured":"Thorup, M.: Quick k-median, k-center, and facility location for sparse graphs. SIAM Journal on Computing\u00a034(2), 405\u2013432 (2005)","journal-title":"SIAM Journal on Computing"},{"issue":"2","key":"7_CR16","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1002\/net.3230170203","volume":"17","author":"P. Winter","year":"1987","unstructured":"Winter, P.: Steiner problem in networks: A survey. Networks\u00a017(2), 129\u2013167 (1987)","journal-title":"Networks"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2010"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-15775-2_7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,2]],"date-time":"2019-06-02T20:19:11Z","timestamp":1559506751000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-15775-2_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642157745","9783642157752"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-15775-2_7","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}