{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T13:22:27Z","timestamp":1742995347936,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662476659"},{"type":"electronic","value":"9783662476666"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"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":[[2015]]},"DOI":"10.1007\/978-3-662-47666-6_54","type":"book-chapter","created":{"date-parts":[[2015,6,19]],"date-time":"2015-06-19T07:46:47Z","timestamp":1434700007000},"page":"675-687","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Optimal Competitiveness for the Rectilinear Steiner Arborescence Problem"],"prefix":"10.1007","author":[{"given":"Erez","family":"Kantor","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shay","family":"Kutten","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,6,20]]},"reference":[{"key":"54_CR1","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1007\/BF02573969","volume":"10","author":"N Alon","year":"1993","unstructured":"Alon, N., Azar, Y.: On-line Steine trees in the euclidean plane. Discrete & Computational Geometry 10, 113\u2013121 (1993)","journal-title":"Discrete & Computational Geometry"},{"key":"54_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"416","DOI":"10.1007\/978-3-642-31585-5_38","volume-title":"Automata, Languages, and Programming","author":"R Bar-Yehuda","year":"2012","unstructured":"Bar-Yehuda, R., Kantor, E., Kutten, S., Rawitz, D.: Growing half-balls: minimizing storage and communication costs in CDNs. In: Czumaj, A., Mehlhorn, K., Pitts, A., Wattenhofer, R. (eds.) ICALP 2012, Part II. LNCS, vol. 7392, pp. 416\u2013427. Springer, Heidelberg (2012)"},{"key":"54_CR3","doi-asserted-by":"crossref","unstructured":"Bein, W., Golin, M., Larmore, L., Zhang, Y.: The Knuth-Yao quadrangle-inequality speedup is a consequence of total monotonicity. ACM Transactions on Algorithms, 6(1) (2009)","DOI":"10.1145\/1644015.1644032"},{"key":"54_CR4","doi-asserted-by":"crossref","unstructured":"Berman, P., Coulston, C.: On-line algorrithms for Steiner tree problems. In: STOC, pp. 344\u2013353 (1997)","DOI":"10.1145\/258533.258618"},{"key":"54_CR5","unstructured":"Charikar, M., Halperin, D., Motwani, R.: The dynamic servers problem. In: 9th Annual Symposium on Discrete Algorithms (SODA), pp. 410\u2013419 (1998)"},{"key":"54_CR6","unstructured":"Cheng, X., Dasgupta, B., Lu, B.: Polynomial time approximation scheme for symmetric rectilinear Steiner arborescence problem. J. Global Optim., 21(4) (2001)"},{"key":"54_CR7","doi-asserted-by":"crossref","unstructured":"Cho, J.D.: A min-cost flow based min-cost rectilinear Steiner distance-preserving tree construction. In: ISPD, pp. 82\u201387 (1997)","DOI":"10.1145\/267665.267692"},{"issue":"1","key":"54_CR8","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1109\/43.673630","volume":"17","author":"J Cong","year":"1998","unstructured":"Cong, J., Kahng, A.B., Leung, K.S.: Efficient algorithms for the minimum shortest path Steiner arborescence problem with applications to VLSI physical design. IEEE Trans. on CAD of Integrated Circuits and Systems 17(1), 24\u201339 (1998)","journal-title":"IEEE Trans. on CAD of Integrated Circuits and Systems"},{"key":"54_CR9","unstructured":"Ladeira de Matos, R.R.: A rectilinear arborescence problem. Dissertation, University of Alabama (1979)"},{"issue":"4","key":"54_CR10","doi-asserted-by":"publisher","first-page":"826","DOI":"10.1137\/0132071","volume":"32","author":"MR Garey","year":"1977","unstructured":"Garey, M.R., Johnson, D.S.: The rectilinear Steiner tree problem is NP-complete. SIAM J. Appl. Math. 32(4), 826\u2013834 (1977)","journal-title":"SIAM J. Appl. Math."},{"key":"54_CR11","unstructured":"Halperin, D., Latombe, J.C., Motwani, R.: Dynamic maintenance of kinematic structures. In: Laumond, J.P., Overmars, M. (eds.) Algorithmic Foundations of Robotics, pp. 155\u2013170. A.K. Peters Publishing (1997)"},{"issue":"1","key":"54_CR12","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1002\/net.3230220105","volume":"22","author":"FK Hwang","year":"1992","unstructured":"Hwang, F.K., Richards, D.S.: Steiner tree problems. Networks 22(1), 55\u2013897 (1992)","journal-title":"Networks"},{"key":"54_CR13","doi-asserted-by":"crossref","unstructured":"Kahng, A., Robins, G.: On optimal interconnects for VLSI. Kluwer Academic Publishers (1995)","DOI":"10.1007\/978-1-4757-2363-2"},{"key":"54_CR14","doi-asserted-by":"crossref","unstructured":"Kantor, E., Kutten, S.: Optimal competitiveness for symmetric rectilinear Steiner arborescence and related problems (2013). CoRR, abs\/1307.3080","DOI":"10.1007\/978-3-662-43951-7_44"},{"key":"54_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"520","DOI":"10.1007\/978-3-662-43951-7_44","volume-title":"Automata, Languages, and Programming","author":"E Kantor","year":"2014","unstructured":"Kantor, E., Kutten, S.: Optimal competitiveness for symmetric rectilinear steiner arborescence and related problems. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds.) ICALP 2014, Part II. LNCS, vol. 8573, pp. 520\u2013531. Springer, Heidelberg (2014)"},{"key":"54_CR16","doi-asserted-by":"crossref","unstructured":"Kantor, E., Kutten, S.: Optimal competitiveness for the rectilinear steiner arborescence problem (2015). CoRR, arxiv.org\/abs\/1504.08265","DOI":"10.1007\/978-3-662-47666-6_54"},{"issue":"3","key":"54_CR17","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1023\/A:1009826311973","volume":"4","author":"B Lu","year":"2000","unstructured":"Lu, B., Ruan, L.: Polynomial time approximation scheme for rectilinear Steiner arborescence problem. Combinatorial Optimization 4(3), 357\u2013363 (2000)","journal-title":"Combinatorial Optimization"},{"key":"54_CR18","first-page":"59","volume":"18","author":"L Nastansky","year":"1974","unstructured":"Nastansky, L., Selkow, S.M., Stewart, N.F.: Cost minimum trees in directed acyclic graphs. Z. Oper. Res. 18, 59\u201367 (1974)","journal-title":"Z. Oper. Res."},{"key":"54_CR19","doi-asserted-by":"crossref","unstructured":"Papadimitriou, C.H., Ramanathan, S., Rangan, P.V.: Information caching for delivery of personalized video programs for home entertainment channels. In: IEEE International Conf. on Multimedia Computing and Systems, pp. 214\u2013223 (1994)","DOI":"10.1109\/MMCS.1994.292456"},{"key":"54_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1007\/BFb0015422","volume-title":"Algorithms and Computations","author":"CH Papadimitriou","year":"1995","unstructured":"Papadimitriou, C.H., Ramanathan, S., Rangan, P.V.: Optimal information delivery. In: Staples, J., Katoh, N., Eades, P., Moffat, A. (eds.) ISAAC 1995. LNCS, vol. 1004, pp. 181\u2013187. Springer, Heidelberg (1995)"},{"issue":"3","key":"54_CR21","doi-asserted-by":"publisher","first-page":"204","DOI":"10.1016\/0140-3664(95)98543-E","volume":"18","author":"CH Papadimitriou","year":"1995","unstructured":"Papadimitriou, C.H., Ramanathan, S., Rangan, P.V., Sampathkumar, S.: Multimedia information caching for personalized video-on demand. Computer Communications 18(3), 204\u2013216 (1995)","journal-title":"Computer Communications"},{"key":"54_CR22","doi-asserted-by":"crossref","unstructured":"Rao, S., Sadayappan, P., Hwang, F., Shor, P.: The Rectilinear Steiner Arborescence problem. Algorithmica, pp. 277\u2013288 (1992)","DOI":"10.1007\/BF01758762"},{"key":"54_CR23","unstructured":"Shi, W., Su, C.: The rectilinear Steiner arborescence problem is NP-complete. In: SODA, pp. 780\u2013787 (2000)"},{"issue":"3","key":"54_CR24","first-page":"320","volume":"21","author":"VA Trubin","year":"1985","unstructured":"Trubin, V.A.: Subclass of the Steiner problems on a plane with rectilinear metric. Cybernetics and Systems Analysis 21(3), 320\u2013324 (1985)","journal-title":"Cybernetics and Systems Analysis"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-47666-6_54","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,21]],"date-time":"2023-02-21T02:09:23Z","timestamp":1676945363000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-662-47666-6_54"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783662476659","9783662476666"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-47666-6_54","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"20 June 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}