{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,5]],"date-time":"2022-04-05T09:49:11Z","timestamp":1649152151032},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2011,6,23]],"date-time":"2011-06-23T00:00:00Z","timestamp":1308787200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Comput Sci Res Dev"],"published-print":{"date-parts":[[2012,8]]},"DOI":"10.1007\/s00450-011-0180-2","type":"journal-article","created":{"date-parts":[[2011,6,22]],"date-time":"2011-06-22T16:26:44Z","timestamp":1308760004000},"page":"217-223","source":"Crossref","is-referenced-by-count":2,"title":["An overview of some results for reordering buffers"],"prefix":"10.1007","volume":"27","author":[{"given":"Matthias","family":"Englert","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2011,6,23]]},"reference":[{"key":"180_CR1","first-page":"84","volume-title":"Proceedings of the 16th ACM symposium on parallel algorithms and architectures (SPAA)","author":"S Albers","year":"2004","unstructured":"Albers S (2004) New results on web caching with request reordering. In: Proceedings of the 16th ACM symposium on parallel algorithms and architectures (SPAA), pp 84\u201392"},{"issue":"2","key":"180_CR2","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1006\/jagm.2001.1182","volume":"41","author":"H Alborzi","year":"2001","unstructured":"Alborzi H, Torng E, Uthaisombut P, Wagner S (2001) The k-client problem. J Algorithms 41(2):115\u2013173","journal-title":"J Algorithms"},{"key":"180_CR3","unstructured":"Asahiro Y, Kawahara K, Miyano E (2010) NP-hardness of the sorting buffer problem on the uniform metric. Unpublished manuscript"},{"issue":"3","key":"180_CR4","doi-asserted-by":"crossref","first-page":"486","DOI":"10.1145\/258128.258201","volume":"44","author":"J Aspnes","year":"1997","unstructured":"Aspnes J, Azar Y, Fiat A, Plotkin SA, Waarts O (1997) On-line routing of virtual circuits with applications to load balancing and machine scheduling. J ACM 44(3):486\u2013504","journal-title":"J ACM"},{"key":"180_CR5","doi-asserted-by":"crossref","unstructured":"Avigdor-Elgrabli N, Rabani Y (2010) An improved competitive algorithm for reordering buffer management. In: Proceedings of the 21st ACM-SIAM symposium on discrete algorithms (SODA), pp.\u00a013\u201321","DOI":"10.1137\/1.9781611973075.2"},{"key":"180_CR6","unstructured":"Azar Y, Gamzu I, Rabani Y (October 2008) Personal communication"},{"issue":"2","key":"180_CR7","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1006\/jagm.1995.1008","volume":"18","author":"Y Azar","year":"1995","unstructured":"Azar Y, Naor J, Rom R (1995) The competitiveness of on-line assignments. J Algorithms 18(2):221\u2013237","journal-title":"J Algorithms"},{"issue":"1","key":"180_CR8","doi-asserted-by":"crossref","first-page":"108","DOI":"10.1006\/jagm.1999.1070","volume":"35","author":"P Berman","year":"2000","unstructured":"Berman P, Charikar M, Karpinski M (2000) On-line load balancing for related machines. J Algorithms 35(1):108\u2013121","journal-title":"J Algorithms"},{"key":"180_CR9","unstructured":"Chan H-L, Megow N, van Stee R, Sitters R (2010) The sorting buffer problem is NP-hard. CoRR, arXiv:1009.4355"},{"issue":"3","key":"180_CR10","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1016\/0167-6377(95)00039-9","volume":"18","author":"B Chen","year":"1995","unstructured":"Chen B, van Vliet A, Woeginger GJ (1995) An optimal algorithm for preemptive on-line scheduling. Oper Res Lett 18(3):127\u2013131","journal-title":"Oper Res Lett"},{"key":"180_CR11","doi-asserted-by":"crossref","unstructured":"D\u00f3sa G, Epstein L (2008) Online scheduling with a buffer on related machines. Journal of Combinatorial Optimization. doi: 10.1007\/s10878-008-9200-y","DOI":"10.1007\/s10878-008-9200-y"},{"key":"180_CR12","first-page":"456","volume-title":"Proceedings of the 17th European symposium on algorithms (ESA)","author":"G D\u00f3sa","year":"2009","unstructured":"D\u00f3sa G, Epstein L (2009) Preemptive online scheduling with reordering. In: Proceedings of the 17th European symposium on algorithms (ESA), pp 456\u2013467"},{"key":"180_CR13","doi-asserted-by":"crossref","first-page":"603","DOI":"10.1109\/FOCS.2008.46","volume-title":"Proceedings of the 49th IEEE symposium on foundations of computer science (FOCS)","author":"M Englert","year":"2008","unstructured":"Englert M, \u00d6zmen D, Westermann M (2008) The power of reordering for online minimum makespan scheduling. In: Proceedings of the 49th IEEE symposium on foundations of computer science (FOCS), pp 603\u2013612"},{"key":"180_CR14","first-page":"556","volume-title":"Proceedings of the 39th ACM symposium on theory of computing (STOC)","author":"M Englert","year":"2007","unstructured":"Englert M, R\u00e4cke H, Westermann M (2007) Reordering buffers for general metric spaces. In: Proceedings of the 39th ACM symposium on theory of computing (STOC), pp 556\u2013564"},{"key":"180_CR15","doi-asserted-by":"crossref","first-page":"627","DOI":"10.1007\/11523468_51","volume-title":"Proceedings of the 32nd international colloquium on automata, languages and programming (ICALP)","author":"M Englert","year":"2005","unstructured":"Englert M, Westermann M (2005) Reordering buffer management for non-uniform cost models. In: Proceedings of the 32nd international colloquium on automata, languages and programming (ICALP), pp 627\u2013638"},{"key":"180_CR16","doi-asserted-by":"crossref","first-page":"336","DOI":"10.1007\/978-3-642-14165-2_29","volume-title":"Proceedings of the 37th international colloquium on automata, languages and programming (ICALP)","author":"L Epstein","year":"2010","unstructured":"Epstein L, Levin A, van Stee R (2010) Max-min online allocations with a reordering buffer. In: Proceedings of the 37th international colloquium on automata, languages and programming (ICALP), pp 336\u2013347"},{"issue":"3","key":"180_CR17","doi-asserted-by":"crossref","first-page":"485","DOI":"10.1016\/j.jcss.2004.04.011","volume":"69","author":"J Fakcharoenphol","year":"2004","unstructured":"Fakcharoenphol J, Rao SB, Talwar K (2004) A tight bound on approximating arbitrary metrics by tree metrics. J Comput Syst Sci 69(3):485\u2013497","journal-title":"J Comput Syst Sci"},{"issue":"2\u20133","key":"180_CR18","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1016\/j.tcs.2004.05.016","volume":"324","author":"T Feder","year":"2004","unstructured":"Feder T, Motwani R, Panigrahy R, Seiden SS, van Stee R, Zhu A (2004) Combining request scheduling with web caching. Theor Comput Sci 324(2\u20133):201\u2013218","journal-title":"Theor Comput Sci"},{"issue":"6","key":"180_CR19","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1002\/1099-1425(200011\/12)3:6<343::AID-JOS54>3.0.CO;2-2","volume":"3","author":"R Fleischer","year":"2000","unstructured":"Fleischer R, Wahl M (2000) On-line scheduling revisited. J Sched 3(6):343\u2013353","journal-title":"J Sched"},{"key":"180_CR20","first-page":"658","volume-title":"Proceedings of the 24th symposium on theoretical aspects of computer science (STACS)","author":"I Gamzu","year":"2007","unstructured":"Gamzu I, Segev D (2007) Improved online algorithms for the sorting buffer problem. In: Proceedings of the 24th symposium on theoretical aspects of computer science (STACS), pp 658\u2013669"},{"issue":"5","key":"180_CR21","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1016\/S0167-6377(98)00005-4","volume":"21","author":"H Kellerer","year":"1997","unstructured":"Kellerer H, Kotov V, Speranza MG, Tuza Z (1997) Semi on-line algorithms for the partition problem. Oper Res Lett 21(5):235\u2013242","journal-title":"Oper Res Lett"},{"key":"180_CR22","first-page":"584","volume-title":"Proceedings of the 23rd symposium on theoretical aspects of computer science (STACS)","author":"R Khandekar","year":"2006","unstructured":"Khandekar R, Pandit V (2006) Online sorting buffers on line. In: Proceedings of the 23rd symposium on theoretical aspects of computer science (STACS), pp 584\u2013595"},{"key":"180_CR23","first-page":"278","volume-title":"Proceedings of the 2nd international multi-symposiums on computer and computational sciences","author":"S Li","year":"2007","unstructured":"Li S, Zhou Y, Sun G, Chen F (2007) Study on parallel machine scheduling problem with buffer. In: Proceedings of the 2nd international multi-symposiums on computer and computational sciences, pp 278\u2013273"},{"issue":"1","key":"180_CR24","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1287\/mnsc.6.1.1","volume":"6","author":"R McNaughton","year":"1959","unstructured":"McNaughton R (1959) Scheduling with deadlines and loss functions. Manag Sci 6(1):1\u201312","journal-title":"Manag Sci"},{"key":"180_CR25","first-page":"820","volume-title":"Proceedings of the 10th European symposium on algorithms (ESA)","author":"H R\u00e4cke","year":"2002","unstructured":"R\u00e4cke H, Sohler C, Westermann M (2002) Online scheduling for sorting buffers. In: Proceedings of the 10th European symposium on algorithms (ESA), pp 820\u2013832"},{"key":"180_CR26","unstructured":"Rudin JF III (2001) Improved bound for the online scheduling problem. PhD thesis, University of Texas at Dallas"},{"issue":"2","key":"180_CR27","doi-asserted-by":"crossref","first-page":"202","DOI":"10.1145\/2786.2793","volume":"28","author":"D Sleator","year":"1985","unstructured":"Sleator D, Tarjan R (1985) Amortized efficiency of list update and paging rules. Commun ACM 28(2):202\u2013208","journal-title":"Commun ACM"},{"issue":"3","key":"180_CR28","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1016\/S0020-0190(97)00006-9","volume":"61","author":"G Zhang","year":"1997","unstructured":"Zhang G (1997) A simple semi on-line algorithm for P2\/\/C max\u2009 with a buffer. Inf Process Lett 61(3):145\u2013148","journal-title":"Inf Process Lett"}],"container-title":["Computer Science - Research and Development"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00450-011-0180-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00450-011-0180-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00450-011-0180-2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T13:32:47Z","timestamp":1559136767000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00450-011-0180-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,6,23]]},"references-count":28,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2012,8]]}},"alternative-id":["180"],"URL":"https:\/\/doi.org\/10.1007\/s00450-011-0180-2","relation":{},"ISSN":["1865-2034","1865-2042"],"issn-type":[{"value":"1865-2034","type":"print"},{"value":"1865-2042","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,6,23]]}}}