{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,7]],"date-time":"2025-10-07T14:35:27Z","timestamp":1759847727470},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2016,6,17]],"date-time":"2016-06-17T00:00:00Z","timestamp":1466121600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Sched"],"published-print":{"date-parts":[[2017,10]]},"DOI":"10.1007\/s10951-016-0487-8","type":"journal-article","created":{"date-parts":[[2016,6,17]],"date-time":"2016-06-17T06:16:59Z","timestamp":1466144219000},"page":"423-442","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Reordering buffer management with advice"],"prefix":"10.1007","volume":"20","author":[{"given":"Anna","family":"Adamaszek","sequence":"first","affiliation":[]},{"given":"Marc P.","family":"Renault","sequence":"additional","affiliation":[]},{"given":"Adi","family":"Ros\u00e9n","sequence":"additional","affiliation":[]},{"given":"Rob","family":"van Stee","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,6,17]]},"reference":[{"key":"487_CR1","first-page":"607","volume-title":"STOC","author":"A Adamaszek","year":"2011","unstructured":"Adamaszek, A., Czumaj, A., Englert, M., & R\u00e4cke, H. (2011). Almost tight bounds for reordering buffer management. In L. Fortnow & S. P. Vadhan (Eds.), STOC (pp. 607\u2013616). San Jose: ACM Press."},{"key":"487_CR2","doi-asserted-by":"publisher","unstructured":"Albers, S., & Hellwig, M. (2014). Online makespan minimization with parallel schedules. In: Ravi, R., G\u00f8rtz, I. L. (eds.) Algorithm theory\u2014SWAT 2014\u201414th Scandinavian symposium and workshops, Copenhagen, July 2\u20134. Proceedings, Lecture notes in computer science (Vol. 8503, pp. 13\u201325). Springer. doi:\n                        10.1007\/978-3-319-08404-6_2\n                        \n                    .","DOI":"10.1007\/978-3-319-08404-6_2"},{"issue":"10\u201311","key":"487_CR3","doi-asserted-by":"crossref","first-page":"1453","DOI":"10.1016\/j.dam.2012.02.005","volume":"160","author":"Y Asahiro","year":"2012","unstructured":"Asahiro, Y., Kawahara, K., & Miyano, E. (2012). Np-hardness of the sorting buffer problem on the uniform metric. Discrete Applied Mathematics, 160(10\u201311), 1453\u20131464.","journal-title":"Discrete Applied Mathematics"},{"key":"487_CR4","first-page":"13","volume-title":"SODA","author":"N Avigdor-Elgrabli","year":"2010","unstructured":"Avigdor-Elgrabli, N., & Rabani, Y. (2010). An improved competitive algorithm for reordering buffer management. In M. Charikar (Ed.), SODA (pp. 13\u201321). Philadelphia: SIAM."},{"key":"487_CR5","first-page":"973","volume-title":"SODA","author":"N Avigdor-Elgrabli","year":"2013","unstructured":"Avigdor-Elgrabli, N., & Rabani, Y. (2013). A constant factor approximation algorithm for reordering buffer management. In S. Khanna (Ed.), SODA (pp. 973\u2013984). Philadelphia: SIAM."},{"key":"487_CR6","doi-asserted-by":"publisher","unstructured":"Avigdor-Elgrabli, N., & Rabani, Y. (2013). An optimal randomized online algorithm for reordering buffer management. In 54th Annual IEEE Symposium on Foundations of Computer Science, (pp.1\u201310). Berkeley, CA. doi:\n                        10.1109\/FOCS.2013.9","DOI":"10.1109\/FOCS.2013.9"},{"key":"487_CR7","doi-asserted-by":"crossref","unstructured":"Blandford, D. K., & Blelloch, G. E. (2002). Index compression through document reordering. In: DCC (pp. 342\u2013351). IEEE Computer Society.","DOI":"10.1109\/DCC.2002.999972"},{"key":"487_CR8","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/j.tcs.2014.06.006","volume":"554","author":"H B\u00f6ckenhauer","year":"2014","unstructured":"B\u00f6ckenhauer, H., Hromkovic, J., Komm, D., Krug, S., Smula, J., & Sprock, A. (2014). The string guessing problem as a method to prove lower bounds on the advice complexity. Theoretical Computer Science, 554, 95\u2013108. doi:\n                        10.1016\/j.tcs.2014.06.006\n                        \n                    .","journal-title":"Theoretical Computer Science"},{"key":"487_CR9","unstructured":"B\u00f6ckenhauer, H. J., Komm, D., Kr\u00e1lovic, R., & Kr\u00e1lovic, R. (2011). On the advice complexity of the k-server problem. In: Aceto, L., Henzinger, M., Sgall, J. (eds.) ICALP (1), Lecture notes in computer science (Vol. 6755, pp 207\u2013218). Springer. Also as technical report at ftp:\/\/ftp.inf.ethz.ch\/pub\/publications\/tech-reports\/7xx\/703.pdf."},{"key":"487_CR10","doi-asserted-by":"crossref","unstructured":"B\u00f6ckenhauer, H. J., Komm, D., Kr\u00e1lovic, R., Kr\u00e1lovic, R., & M\u00f6mke, T. (2009). On the advice complexity of online problems. In: Dong, Y., Du, D.Z., Ibarra, O.H. (eds.) ISAAC, Lecture notes in computer science (Vol. 5878, pp. 331\u2013340). Berlin: Springer.","DOI":"10.1007\/978-3-642-10631-6_35"},{"key":"487_CR11","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1016\/j.tcs.2011.12.077","volume":"423","author":"HL Chan","year":"2012","unstructured":"Chan, H. L., Megow, N., Sitters, R., & van Stee, R. (2012). A note on sorting buffers offline. Theoretical Computer Science, 423, 11\u201318.","journal-title":"Theoretical Computer Science"},{"key":"487_CR12","doi-asserted-by":"crossref","unstructured":"Dobrev, S., Kr\u00e1lovi\u010d, R., & Pardubsk\u00e1, D. (2008). How much information about the future is needed? In: SOFSEM\u201908: Proceedings of the 34th conference on current trends in theory and practice of computer science (pp. 247\u2013258). Berlin, Heidelberg: Springer.","DOI":"10.1007\/978-3-540-77566-9_21"},{"key":"487_CR13","doi-asserted-by":"publisher","unstructured":"Dohrau, J. (2015). Online makespan scheduling with sublinear advice. In: Italiano, G. F., Margaria-Steffen, T., Pokorn\u00fd, J., Quisquater, J., Wattenhofer, R. (eds.) SOFSEM 2015: Theory and practice of computer science\u201441st international conference on current trends in theory and practice of computer science, Pec pod Sn\u011b\u017ekou, Czech Republic, January 24\u201329, 2015. Proceedings, Lecture Notes in Computer Science (Vol. 8939, pp. 177\u2013188). Springer. doi:\n                        10.1007\/978-3-662-46078-8_15\n                        \n                    .","DOI":"10.1007\/978-3-662-46078-8_15"},{"key":"487_CR14","doi-asserted-by":"crossref","unstructured":"Dorrigiv, R., He, M., & Zeh, N. (2012). On the advice complexity of buffer management. In: Chao, K. M., Sheng Hsu, T., Lee, D. T. (eds.) ISAAC, Lecture notes in computer science (Vol. 7676, pp. 136\u2013145). New York: Springer.","DOI":"10.1007\/978-3-642-35261-4_17"},{"issue":"24","key":"487_CR15","doi-asserted-by":"crossref","first-page":"2642","DOI":"10.1016\/j.tcs.2010.08.007","volume":"412","author":"Y Emek","year":"2011","unstructured":"Emek, Y., Fraigniaud, P., Korman, A., & Ros\u00e9n, A. (2011). Online computation with advice. Theoretical Computer Science, 412(24), 2642\u20132656.","journal-title":"Theoretical Computer Science"},{"issue":"1","key":"487_CR16","doi-asserted-by":"crossref","first-page":"27","DOI":"10.4086\/toc.2010.v006a002","volume":"6","author":"M Englert","year":"2010","unstructured":"Englert, M., R\u00e4cke, H., & Westermann, M. (2010). Reordering buffers for general metric spaces. Theory of Computing, 6(1), 27\u201346.","journal-title":"Theory of Computing"},{"key":"487_CR17","doi-asserted-by":"crossref","unstructured":"Englert, M., & Westermann, M. (2005). Reordering buffer management for non-uniform cost models. In: Caires, L., Italiano, G. F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP, Lecture notes in computer science (Vol. 3580, pp 627\u2013638). Berlin: Springer.","DOI":"10.1007\/11523468_51"},{"issue":"9","key":"487_CR18","doi-asserted-by":"publisher","first-page":"1865","DOI":"10.1080\/00207540310001646821","volume":"42","author":"K Gutenschwager","year":"2004","unstructured":"Gutenschwager, K., Spiekermann, S., & Vo\u00df, S. (2004). A sequential ordering problem in automotive paint shops. International Journal of Production Research, 42(9), 1865\u20131878. doi:\n                        10.1080\/00207540310001646821\n                        \n                    .","journal-title":"International Journal of Production Research"},{"key":"487_CR19","doi-asserted-by":"crossref","unstructured":"Hromkovic, J., Kr\u00e1lovic, R., & Kr\u00e1lovic, R. (2010). Information complexity of online problems. In: Hlinen\u00fd, P., Kucera, A. (eds.) MFCS, Lecture notes in computer science (Vol. 6281, pp 24\u201336). Berlin: Springer.","DOI":"10.1007\/978-3-642-15155-2_3"},{"issue":"2","key":"487_CR20","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1051\/ita\/2011105","volume":"45","author":"D Komm","year":"2011","unstructured":"Komm, D., & Kr\u00e1lovic, R. (2011). Advice complexity and barely random algorithms. RAIRO-Theoretical Informatics and Applications, 45(2), 249\u2013267.","journal-title":"RAIRO-Theoretical Informatics and Applications"},{"key":"487_CR21","unstructured":"Krokowski, J., R\u00e4cke, H., Sohler, C., & Westermann, M. (2004). Reducing state changes with a pipeline buffer. In: Girod, B., Magnor, M. A., Seidel, H. P. (eds.) VMV (p. 217). Aka GmbH."},{"key":"487_CR22","volume-title":"Elements of the theory of computation","author":"HR Lewis","year":"1997","unstructured":"Lewis, H. R., & Papadimitriou, C. H. (1997). Elements of the theory of computation (2nd ed.). Upper Saddle River, NJ: Prentice Hall PTR.","edition":"2"},{"key":"487_CR23","doi-asserted-by":"crossref","unstructured":"R\u00e4cke, H., Sohler, C., & Westermann, M. (2002). Online scheduling for sorting buffers. In: M\u00f6hring, R. H., Raman, R. (eds.) ESA, Lecture Notes in Computer Science (Vol. 2461, pp. 820\u2013832). Berlin: Springer.","DOI":"10.1007\/3-540-45749-6_71"},{"key":"487_CR24","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00224-012-9434-z","volume":"56","author":"MP Renault","year":"2012","unstructured":"Renault, M. P., & Ros\u00e9n, A. (2012). On online algorithms with advice for the k-server problem. Theory of Computing Systems, 56, 1\u201319. doi:\n                        10.1007\/s00224-012-9434-z\n                        \n                    .","journal-title":"Theory of Computing Systems"},{"key":"487_CR25","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1016\/j.tcs.2015.07.050","volume":"600","author":"MP Renault","year":"2015","unstructured":"Renault, M. P., Ros\u00e9n, A., & van Stee, R. (2015). Online algorithms with advice for bin packing and scheduling problems. Theoretical Computer Science, 600, 155\u2013170. doi:\n                        10.1016\/j.tcs.2015.07.050\n                        \n                    .","journal-title":"Theoretical Computer Science"},{"key":"487_CR26","doi-asserted-by":"publisher","unstructured":"Standard for information technology portable operating system interface (posix(r)) base specifications, issue 7. IEEE Std 1003.1, 2013 Edition (incorporates IEEE Std 1003.1-2008, and IEEE Std 1003.1-2008\/Cor 1-2013) pp. 1\u20133906 (2013). doi:\n                        10.1109\/IEEESTD.2013.6506091\n                        \n                    .","DOI":"10.1109\/IEEESTD.2013.6506091"}],"container-title":["Journal of Scheduling"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10951-016-0487-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-016-0487-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-016-0487-8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-016-0487-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,9,27]],"date-time":"2017-09-27T09:59:09Z","timestamp":1506506349000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10951-016-0487-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,6,17]]},"references-count":26,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2017,10]]}},"alternative-id":["487"],"URL":"https:\/\/doi.org\/10.1007\/s10951-016-0487-8","relation":{},"ISSN":["1094-6136","1099-1425"],"issn-type":[{"value":"1094-6136","type":"print"},{"value":"1099-1425","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,6,17]]}}}