{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T05:06:10Z","timestamp":1750309570831,"version":"3.41.0"},"reference-count":36,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2024,10,11]],"date-time":"2024-10-11T00:00:00Z","timestamp":1728604800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"DFG","award":["AN 1262\/1-1"],"award-info":[{"award-number":["AN 1262\/1-1"]}]},{"DOI":"10.13039\/501100001824","name":"GA \u010cR","doi-asserted-by":"crossref","award":["22-22997S"],"award-info":[{"award-number":["22-22997S"]}],"id":[{"id":"10.13039\/501100001824","id-type":"DOI","asserted-by":"crossref"}]},{"name":"European Research Council","award":["ERC-2014-CoG 647557"],"award-info":[{"award-number":["ERC-2014-CoG 647557"]}]},{"name":"Center for Foundations of Modern Computer Science","award":["UNCE 24\/SCI\/008"],"award-info":[{"award-number":["UNCE 24\/SCI\/008"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2024,10,31]]},"abstract":"<jats:p>We consider the problem of managing the buffer of a shared-memory switch that transmits packets of unit value. A shared-memory switch consists of an input port, a number of output ports, and a buffer with a specific capacity. In each time step, an arbitrary number of packets arrive at the input port, each packet designated for one output port. Each packet is added to the queue of the respective output port. If the total number of packets exceeds the capacity of the buffer, some packets have to be irrevocably evicted. At the end of each time step, each output port transmits a packet in its queue, and the goal is to maximize the number of transmitted packets.<\/jats:p>\n          <jats:p>\n            The Longest Queue Drop (\n            <jats:monospace>LQD<\/jats:monospace>\n            ) online algorithm accepts any arriving packet to the buffer. However, if this results in the buffer exceeding its memory capacity, then\n            <jats:monospace>LQD<\/jats:monospace>\n            drops a packet from whichever queue is currently the longest, breaking ties arbitrarily. The\n            <jats:monospace>LQD<\/jats:monospace>\n            algorithm was first introduced in 1991, and has been known to be\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(2\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            -competitive since 2001. Although\n            <jats:monospace>LQD<\/jats:monospace>\n            remains the best known online algorithm for the problem and is of practical interest, determining its true competitiveness is a long-standing open problem. We show that\n            <jats:monospace>LQD<\/jats:monospace>\n            is 1.6918-competitive, establishing the first\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\((2-\\varepsilon)\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            upper bound for the competitive ratio of\n            <jats:monospace>LQD<\/jats:monospace>\n            for a constant\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\varepsilon{\\,\\gt\\,}0\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            .\n          <\/jats:p>","DOI":"10.1145\/3676887","type":"journal-article","created":{"date-parts":[[2024,7,12]],"date-time":"2024-07-12T16:30:59Z","timestamp":1720801859000},"page":"1-29","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Breaking the Barrier of 2 for the Competitiveness of Longest Queue Drop"],"prefix":"10.1145","volume":"20","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2152-7883","authenticated-orcid":false,"given":"Antonios","family":"Antoniadis","sequence":"first","affiliation":[{"name":"University of Twente, Enschede, The Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8859-7731","authenticated-orcid":false,"given":"Matthias","family":"Englert","sequence":"additional","affiliation":[{"name":"University of Warwick, Coventry, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0386-749X","authenticated-orcid":false,"given":"Nicolaos","family":"Matsakis","sequence":"additional","affiliation":[{"name":"Computer Science Institute of Charles University, Prague, Czech Republic"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1169-7934","authenticated-orcid":false,"given":"Pavel","family":"Vesel\u00fd","sequence":"additional","affiliation":[{"name":"Computer Science Institute of Charles University, Prague, Czech Republic"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,10,11]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/1435375.1435378"},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.5555\/3288645.3288665"},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704446268"},{"key":"e_1_3_3_5_2","first-page":"761","volume-title":"Proceedings of the 14th ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Andelman N.","year":"2003","unstructured":"N. Andelman, Y. Mansour, and A. Zhu. 2003. Competitive queueing policies for QoS switches. In Proceedings of the 14th ACM-SIAM Symposium on Discrete Algorithms (SODA). 761\u2013770."},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-005-1190-x"},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-005-1159-9"},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-27836-8_19"},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2011.05.015"},{"key":"e_1_3_3_10_2","unstructured":"I. Bochkov A. Davydow N. Gaevoy and S. I. Nikolenko. 2019. New competitiveness bounds for the shared memory switch. arXiv:1907.04399. Retrieved from https:\/\/arxiv.org\/abs\/1907.04399"},{"key":"e_1_3_3_11_2","first-page":"148","article-title":"Early fair drop: A new buffer management policy","volume":"3654","author":"Bruno J. L.","year":"1998","unstructured":"J. L. Bruno, B. \u00d6zden, A. Silberschatz, and H. Saran. 1998. Early fair drop: A new buffer management policy. Multimedia Computing and Networking 3654 (1998), 148\u2013161.","journal-title":"Multimedia Computing and Networking"},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICC.2000.853677"},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.5555\/559768"},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.5555\/1202844"},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2005.03.005"},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-003-1025-6"},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/1290672.1290687"},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-008-9236-5"},{"key":"e_1_3_3_19_2","doi-asserted-by":"publisher","DOI":"10.1137\/110856745"},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS.2014.55"},{"key":"e_1_3_3_21_2","doi-asserted-by":"publisher","DOI":"10.1145\/1753171.1753195"},{"key":"e_1_3_3_22_2","first-page":"53","volume-title":"Proceedings of the 13th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)","author":"Hahne E. L.","year":"2001","unstructured":"E. L. Hahne, A. Kesselman, and Y. Mansour. 2001. Competitive buffer management for shared-memory switches. In Proceedings of the 13th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). 53\u201358."},{"key":"e_1_3_3_23_2","first-page":"434","volume-title":"Proceedings of the 35th Conference on Information Sciences and Systems","author":"Hajek B.","year":"2001","unstructured":"B. Hajek. 2001. On the competitiveness of on-line scheduling of unit-length packets with hard deadlines in slotted time. In Proceedings of the 35th Conference on Information Sciences and Systems. 434\u2013438."},{"key":"e_1_3_3_24_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-012-9700-0"},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701399666"},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.05.014"},{"key":"e_1_3_3_27_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-005-1158-x"},{"key":"e_1_3_3_28_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2004.09.003"},{"key":"e_1_3_3_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/1248377.1248437"},{"key":"e_1_3_3_30_2","first-page":"199","volume-title":"Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Li F.","year":"2007","unstructured":"F. Li, J. Sethuraman, and C. Stein. 2007. Better online buffer management. In Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms (SODA). 199\u2013208."},{"key":"e_1_3_3_31_2","volume-title":"Approximation Algorithms for Packing and Buffering problems","author":"Matsakis N.","year":"2015","unstructured":"N. Matsakis. 2015. Approximation Algorithms for Packing and Buffering problems. PhD thesis. University of Warwick, UK."},{"key":"e_1_3_3_32_2","doi-asserted-by":"publisher","DOI":"10.1049\/ip-com:20045217"},{"key":"e_1_3_3_33_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4939-2864-4_535"},{"key":"e_1_3_3_34_2","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.1998.659666"},{"key":"e_1_3_3_35_2","doi-asserted-by":"publisher","DOI":"10.1137\/21M1469753"},{"key":"e_1_3_3_36_2","doi-asserted-by":"publisher","DOI":"10.1109\/GLOCOM.1991.188515"},{"key":"e_1_3_3_37_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2004.04.007"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3676887","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3676887","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:19:12Z","timestamp":1750295952000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3676887"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,10,11]]},"references-count":36,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,10,31]]}},"alternative-id":["10.1145\/3676887"],"URL":"https:\/\/doi.org\/10.1145\/3676887","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2024,10,11]]},"assertion":[{"value":"2023-02-08","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-06-18","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-10-11","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}