{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,1,7]],"date-time":"2023-01-07T07:13:52Z","timestamp":1673075632446},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2016,7,11]],"date-time":"2016-07-11T00:00:00Z","timestamp":1468195200000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Max Planck Institute for Informatics"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2017,7]]},"DOI":"10.1007\/s00453-016-0177-0","type":"journal-article","created":{"date-parts":[[2016,7,11]],"date-time":"2016-07-11T13:53:05Z","timestamp":1468245185000},"page":"819-868","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Online Packet-Routing in Grids with Bounded Buffers"],"prefix":"10.1007","volume":"78","author":[{"given":"Guy","family":"Even","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Moti","family":"Medina","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,7,11]]},"reference":[{"key":"177_CR1","unstructured":"Awerbuch, B., Azar, Y., Amos, F.: Packet routing via min-cost circuit routing. In: ISTCS, pp. 37\u201342 (1996)"},{"key":"177_CR2","doi-asserted-by":"crossref","unstructured":"Awerbuch, B., Azar, Y., Plotkin, S.: Throughput-competitive on-line routing. In: FOCS\u201993: Proceedings of the 1993 IEEE 34th Annual Foundations of Computer Science, pp. 32\u201340. IEEE Computer Society, Washington (1993)","DOI":"10.1109\/SFCS.1993.366884"},{"issue":"1","key":"177_CR3","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1007\/s00453-007-9143-1","volume":"55","author":"S Angelov","year":"2009","unstructured":"Angelov, S., Khanna, S., Kunal, K.: The network asa storage device: dynamic routing with bounded buffers. Algorithmica 55(1), 71\u201394 (2009). (Appeared in APPROX-05)","journal-title":"Algorithmica"},{"key":"177_CR4","unstructured":"Aiello, W., Kushilevitz, E., Ostrovsky, R., Ros\u00e9n, A.: Dynamic routing on networks with fixed-size buffers. In: SODA, pp. 771\u2013780 (2003)"},{"issue":"2","key":"177_CR5","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1007\/s00453-002-1019-9","volume":"36","author":"M Adler","year":"2003","unstructured":"Adler, M., Khanna, S., Rajaraman, R., Ros\u00e9n, A.: Time-constrained scheduling of weighted packets on trees and meshes. Algorithmica 36(2), 123\u2013152 (2003)","journal-title":"Algorithmica"},{"issue":"6","key":"177_CR6","doi-asserted-by":"crossref","first-page":"599","DOI":"10.1007\/s00224-002-1001-6","volume":"35","author":"M Adler","year":"2002","unstructured":"Adler, M., Rosenberg, A.L., Sitaraman, R.K., Unger, W.: Scheduling time-constrained communication in linear networks. Theory Comput. Syst. 35(6), 599\u2013623 (2002)","journal-title":"Theory Comput. Syst."},{"key":"177_CR7","unstructured":"Azar, Y., Zachut, R.: Packet routing and information gathering in lines, rings and trees. In: ESA, pp. 484\u2013495 (2005). See also manuscript in http:\/\/www.cs.tau.ac.il\/~azar\/"},{"key":"177_CR8","volume-title":"Online Computation and Competitive Analysis","author":"A Borodin","year":"1998","unstructured":"Borodin, A., El-Yaniv, R.: Online Computation and Competitive Analysis. Cambridge University Press, New York (1998)"},{"key":"177_CR9","doi-asserted-by":"crossref","unstructured":"Bartal, Y., Leonardi, S.: On-line routing in all-optical networks. In: ICALP, pp. 516\u2013526 (1997)","DOI":"10.1007\/3-540-63165-8_207"},{"key":"177_CR10","doi-asserted-by":"crossref","unstructured":"Buchbinder, N., Naor, J.: Improved bounds for online routing and packing via a primal-dual approach. In: Annual IEEE Symposium on Foundations of Computer Science, pp. 293\u2013304 (2006)","DOI":"10.1109\/FOCS.2006.39"},{"issue":"2\u20133","key":"177_CR11","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1561\/0400000024","volume":"3","author":"N Buchbinder","year":"2009","unstructured":"Buchbinder, N., Naor, J.S.: The design of competitive online algorithms via a primal-dual approach. Found. Trends Theor. Comput. Sci. 3(2\u20133), 99\u2013263 (2009)","journal-title":"Found. Trends Theor. Comput. Sci."},{"issue":"2","key":"177_CR12","doi-asserted-by":"crossref","first-page":"270","DOI":"10.1287\/moor.1080.0363","volume":"34","author":"N Buchbinder","year":"2009","unstructured":"Buchbinder, N., Naor, J.S.: Online primal-dual algorithms for covering and packing. Math. Oper. Res. 34(2), 270\u2013286 (2009)","journal-title":"Math. Oper. Res."},{"key":"177_CR13","doi-asserted-by":"crossref","unstructured":"Even, G., Medina, M.: An $${o}(log\\mathit{n})$$ o ( l o g n ) -competitive online centralized randomized packet-routing algorithm for lines. In: Abramsky, S., Gavoille, C., Kirchner, C., auf der Heide, F.M., Spirakis, P.G. (eds.) ICALP (2), volume 6199 of Lecture Notes in Computer Science, pp. 139\u2013150. Springer (2010)","DOI":"10.1007\/978-3-642-14162-1_12"},{"key":"177_CR14","doi-asserted-by":"crossref","unstructured":"Even, G., Medina, M.: Online packet-routing in grids with bounded buffers. In: Rajaraman, R., auf der Heide, F.M. (eds) SPAA, pp. 215\u2013224. ACM (2011)","DOI":"10.1145\/1989493.1989525"},{"key":"177_CR15","doi-asserted-by":"crossref","unstructured":"Even, G., Medina, M., Patt-Shamir, B.: Better deterministic online packet routing on grids. In: Proceedings of the 27th ACM on Symposium on Parallelism in Algorithms and Architectures, SPAA 2015, Portland, OR, USA, June 13\u201315, 2015, pp. 284\u2013293 (2015)","DOI":"10.1145\/2755573.2755588"},{"key":"177_CR16","unstructured":"Even, G., Medina, M., Ros\u00e9n, A.: A constant approximation algorithm for scheduling packets on line networks. CoRR. arXiv:1602.06174 , 2016. ESA (2016)"},{"issue":"4","key":"177_CR17","doi-asserted-by":"crossref","first-page":"459","DOI":"10.1002\/net.3230120410","volume":"12","author":"UI Gupta","year":"1982","unstructured":"Gupta, U.I., Lee, D.T., Leung, J.Y.-T.: Efficient algorithms for interval graphs and circular-arc graphs. Networks 12(4), 459\u2013467 (1982)","journal-title":"Networks"},{"key":"177_CR18","unstructured":"Kleinberg, J.M., Tardos, \u00c9.: Disjoint paths in densely embedded graphs. In: FOCS, pp. 52\u201361 (1995). See also manuscript in http:\/\/www.cs.cornell.edu\/home\/kleinber\/"},{"issue":"2","key":"177_CR19","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1007\/BF01215349","volume":"14","author":"FT Leighton","year":"1994","unstructured":"Leighton, F.T., Maggs, B.M., Rao, S.B.: Packet routing and job-shop scheduling in $$O(congestion+ dilation)$$ O ( c o n g e s t i o n + d i l a t i o n ) steps. Combinatorica 14(2), 167\u2013186 (1994)","journal-title":"Combinatorica"},{"issue":"3","key":"177_CR20","doi-asserted-by":"crossref","first-page":"375","DOI":"10.1007\/s004930050061","volume":"19","author":"T Leighton","year":"1999","unstructured":"Leighton, T., Maggs, B., Richa, A.W.: Fast algorithms for finding $$O(congestion+ dilation)$$ O ( c o n g e s t i o n + d i l a t i o n ) packet routing schedules. Combinatorica 19(3), 375\u2013401 (1999)","journal-title":"Combinatorica"},{"key":"177_CR21","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511813603","volume-title":"Probability and Computing: Randomized Algorithms and Probabilistic Analysis","author":"M Mitzenmacher","year":"2005","unstructured":"Mitzenmacher, M., Upfal, E.: Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, Cambridge (2005)"},{"key":"177_CR22","doi-asserted-by":"crossref","unstructured":"R\u00e4cke, H., Ros\u00e9n, A.: Approximation algorithms for time-constrained scheduling on line networks. In: SPAA, pp. 337\u2013346 (2009)","DOI":"10.1145\/1583991.1584071"},{"key":"177_CR23","doi-asserted-by":"crossref","unstructured":"Rabani, Y., Tardos, \u00c9.: Distributed packet switching in arbitrary networks. In: STOC\u201996: Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, pp. 366\u2013375. ACM, New York (1996)","DOI":"10.1145\/237814.237983"},{"key":"177_CR24","doi-asserted-by":"crossref","unstructured":"Srinivasan, A., Teo, C.P.: A constant-factor approximation algorithm for packet routing, and balancing local vs. global criteria. In: Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, pp. 636\u2013643. ACM (1997)","DOI":"10.1145\/258533.258658"},{"issue":"4","key":"177_CR25","doi-asserted-by":"crossref","first-page":"1017","DOI":"10.1109\/TNET.2008.2006221","volume":"17","author":"JS Turner","year":"2009","unstructured":"Turner, J.S.: Strong performance guarantees for asynchronous buffered crossbar scheduler. IEEE\/ACM Trans. Netw. 17(4), 1017\u20131028 (2009)","journal-title":"IEEE\/ACM Trans. Netw."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-016-0177-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0177-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0177-0","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0177-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,11]],"date-time":"2019-09-11T00:25:16Z","timestamp":1568161516000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-016-0177-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,7,11]]},"references-count":25,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2017,7]]}},"alternative-id":["177"],"URL":"https:\/\/doi.org\/10.1007\/s00453-016-0177-0","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,7,11]]}}}