{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T16:45:21Z","timestamp":1787503521473,"version":"build-2736575974"},"reference-count":32,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2015,6,23]],"date-time":"2015-06-23T00:00:00Z","timestamp":1435017600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["856\/11"],"award-info":[{"award-number":["856\/11"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2015,6,23]]},"abstract":"<jats:p>\n                    We design and analyze an online reordering buffer management algorithm with improved\n                    <jats:italic>O<\/jats:italic>\n                    (log\u2009\n                    <jats:italic>k<\/jats:italic>\n                    \/log\u2009log\u2009\n                    <jats:italic>k<\/jats:italic>\n                    ) competitive ratio for nonuniform costs, where\n                    <jats:italic>k<\/jats:italic>\n                    is the buffer size. This improves on the best previous result (even for uniform costs) of Englert and Westermann (2005) giving\n                    <jats:italic>O<\/jats:italic>\n                    (log\u2009\n                    <jats:italic>k<\/jats:italic>\n                    ) competitive ratio, which was also the best (offline) polynomial time approximation guarantee for this problem. Our analysis is based on an intricate dual fitting argument using a linear programming relaxation for the problem that we introduce in this article.\n                  <\/jats:p>","DOI":"10.1145\/2663347","type":"journal-article","created":{"date-parts":[[2015,6,25]],"date-time":"2015-06-25T10:36:19Z","timestamp":1435228579000},"page":"1-15","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["An Improved Competitive Algorithm for Reordering Buffer Management"],"prefix":"10.1145","volume":"11","author":[{"given":"Noa","family":"Avigdor-Elgrabli","sequence":"first","affiliation":[{"name":"Yahoo! Labs, Haifa, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yuval","family":"Rabani","sequence":"additional","affiliation":[{"name":"The Hebrew University of Jerusalem, Jerusalem, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2015,6,23]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Amjad Aboud. 2008. Correlation clustering with penalties and approximating the reordering buffer management problem. Masters thesis Computer Science Department The Technion \u2014 Israel Institute of Technology. Amjad Aboud. 2008. Correlation clustering with penalties and approximating the reordering buffer management problem. Masters thesis Computer Science Department The Technion \u2014 Israel Institute of Technology."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993717"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214031"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-008-9276-x"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2001.1182"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/060661946"},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","unstructured":"Noa Avigdor-Elgrabli Sungjin Im Benjamin Moseley and Yuval Rabani. 2015. On the randomized competitive ratio of reordering buffer management with non-uniform costs. In ICALP (in press). Noa Avigdor-Elgrabli Sungjin Im Benjamin Moseley and Yuval Rabani. 2015. On the randomized competitive ratio of reordering buffer management with non-uniform costs. In ICALP (in press).","DOI":"10.1007\/978-3-662-47672-7_7"},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","unstructured":"Noa Avigdor-Elgrabli and Yuval Rabani. 2013a. A constant factor approximation algorithm for reordering buffer management. In SODA. Noa Avigdor-Elgrabli and Yuval Rabani. 2013a. A constant factor approximation algorithm for reordering buffer management. In SODA.","DOI":"10.1109\/FOCS.2013.9"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.9"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2006.08.001"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276725"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/882455.875020"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/11561071_61"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000024"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2011.12.077"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1378533.1378544"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/130919738"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2010.v006a002"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/11523468_51"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-43948-7_39"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.04.011"},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, David Eppstein (Ed.). ACM\/SIAM, 104--105","author":"Feder Tom\u00e1s","year":"2002","unstructured":"Tom\u00e1s Feder , Rajeev Motwani , Rina Panigrahy , and An Zhu . 2002 . Web caching with request reordering . In Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, David Eppstein (Ed.). ACM\/SIAM, 104--105 . Tom\u00e1s Feder, Rajeev Motwani, Rina Panigrahy, and An Zhu. 2002. Web caching with request reordering. In Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, David Eppstein (Ed.). ACM\/SIAM, 104--105."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2006.03.001"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1644015.1644030"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1080\/00207540310001646821"},{"key":"e_1_2_1_26_1","doi-asserted-by":"crossref","unstructured":"Sungjin Im and Benjamin Moseley. 2014. New approximations for reordering buffer management. In SODA. 1093--1111. Sungjin Im and Benjamin Moseley. 2014. New approximations for reordering buffer management. In SODA. 1093--1111.","DOI":"10.1137\/1.9781611973402.81"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/11672142_48"},{"key":"e_1_2_1_28_1","volume-title":"Kohrt and Kirk Pruhs","author":"Jens","year":"2004","unstructured":"Jens S. Kohrt and Kirk Pruhs . 2004 . A constant approximation algorithm for sorting buffers. In LATIN. 193--202. Jens S. Kohrt and Kirk Pruhs. 2004. A constant approximation algorithm for sorting buffers. In LATIN. 193--202."},{"key":"e_1_2_1_29_1","unstructured":"Jens Krokowski Harald R\u00e4cke Christian Sohler and Matthias Westermann. 2004. Reducing state changes with a pipeline buffer. In VMV. 217. Jens Krokowski Harald R\u00e4cke Christian Sohler and Matthias Westermann. 2004. Reducing state changes with a pipeline buffer. In VMV. 217."},{"key":"e_1_2_1_30_1","doi-asserted-by":"crossref","unstructured":"Harald R\u00e4cke Christian Sohler and Matthias Westermann. 2002. Online scheduling for sorting buffers. In ESA. 820--832. Harald R\u00e4cke Christian Sohler and Matthias Westermann. 2002. Online scheduling for sorting buffers. In ESA. 820--832.","DOI":"10.1007\/3-540-45749-6_71"},{"key":"e_1_2_1_31_1","volume-title":"Applied Operating System Concepts","author":"Silberschatz Abraham","unstructured":"Abraham Silberschatz , Peter Galvin , and Greg Gagne . 2000. Applied Operating System Concepts , 1 st ed. John Wiley , New York, NY . Abraham Silberschatz, Peter Galvin, and Greg Gagne. 2000. Applied Operating System Concepts, 1st ed. John Wiley, New York, NY.","edition":"1"},{"key":"e_1_2_1_32_1","volume-title":"Approximation Algorithms","author":"Vazirani V. V.","unstructured":"V. V. Vazirani . 2001. Approximation Algorithms . Springer , New York, NY . V. V. Vazirani. 2001. Approximation Algorithms. Springer, New York, NY."}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2663347","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2663347","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:12:47Z","timestamp":1750212767000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2663347"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,6,23]]},"references-count":32,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2015,6,23]]}},"alternative-id":["10.1145\/2663347"],"URL":"https:\/\/doi.org\/10.1145\/2663347","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,6,23]]},"assertion":[{"value":"2013-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-06-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}