{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,12]],"date-time":"2025-11-12T03:26:47Z","timestamp":1762918007790,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":43,"publisher":"ACM","license":[{"start":{"date-parts":[[2019,6,23]],"date-time":"2019-06-23T00:00:00Z","timestamp":1561248000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF 805476, CCF 822388, CNS 1408695, FTS 1120129-1-69159, CNS 1755615, CCF 1439084, CCF 1725543, SPX CSR 1763680, CCF 1716252, CCF 1617618, CCF 1314547, CCF 1533644"],"award-info":[{"award-number":["CCF 805476, CCF 822388, CNS 1408695, FTS 1120129-1-69159, CNS 1755615, CCF 1439084, CCF 1725543, SPX CSR 1763680, CCF 1716252, CCF 1617618, CCF 1314547, CCF 1533644"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2019,6,23]]},"DOI":"10.1145\/3313276.3316342","type":"proceedings-article","created":{"date-parts":[[2019,6,20]],"date-time":"2019-06-20T12:19:08Z","timestamp":1561033148000},"page":"1148-1157","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["Achieving optimal backlog in multi-processor cup games"],"prefix":"10.1145","author":[{"given":"Michael A.","family":"Bender","sequence":"first","affiliation":[{"name":"Stony Brook University, USA"}]},{"given":"Mart\u00edn","family":"Farach-Colton","sequence":"additional","affiliation":[{"name":"Rutgers University, USA"}]},{"given":"William","family":"Kuszmaul","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}]}],"member":"320","published-online":{"date-parts":[[2019,6,23]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"Paul Goldberg, and Mike Paterson.","author":"Adler Micah","year":"2003","unstructured":"Micah Adler , Petra Berenbrink , Tom Friedetzky , Leslie Ann Goldberg , Paul Goldberg, and Mike Paterson. 2003 . Micah Adler, Petra Berenbrink, Tom Friedetzky, Leslie Ann Goldberg, Paul Goldberg, and Mike Paterson. 2003."},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/777412.777430"},{"key":"e_1_3_2_1_3_1","unstructured":"Noga Alon and Joel H Spencer. 2004.  Noga Alon and Joel H Spencer. 2004."},{"key":"e_1_3_2_1_4_1","unstructured":"The probabilistic method. John Wiley & Sons.  The probabilistic method. John Wiley & Sons."},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1995.1090"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/110836377"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-005-1190-x"},{"key":"e_1_3_2_1_8_1","unstructured":"Amotz Bar-Noy Ari Freund Shimon Landa and Joseph (Seffi) Naor. 2002.  Amotz Bar-Noy Ari Freund Shimon Landa and Joseph (Seffi) Naor. 2002."},{"volume-title":"On-line Switching Policies. In Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 525\u2013534","author":"Competitive","key":"e_1_3_2_1_9_1","unstructured":"Competitive On-line Switching Policies. In Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 525\u2013534 . http: \/\/dl.acm.org\/citation.cfm?id=545381.545452 Competitive On-line Switching Policies. In Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 525\u2013534. http: \/\/dl.acm.org\/citation.cfm?id=545381.545452"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-002-0085-1"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01940883"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/645605.663243"},{"key":"e_1_3_2_1_13_1","volume-title":"Achieving Optimal Backlog in Multi-Processor Cup Games. arXiv preprint arXiv:1904.02861","author":"Bender Michael","year":"2019","unstructured":"Michael Bender , Mart\u00edn Farach-Colton , and William Kuszmaul . 2019. Achieving Optimal Backlog in Multi-Processor Cup Games. arXiv preprint arXiv:1904.02861 ( 2019 ). Michael Bender, Mart\u00edn Farach-Colton, and William Kuszmaul. 2019. Achieving Optimal Backlog in Multi-Processor Cup Games. arXiv preprint arXiv:1904.02861 (2019)."},{"key":"e_1_3_2_1_14_1","volume-title":"Proceedings of the Symposium on Discrete Algorithms (SODA). 2527\u20132546","author":"Bender Michael A","year":"2018","unstructured":"Michael A Bender , Jake Christensen , Alex Conway , Mart\u00edn Farach-Colton , Rob Johnson , and Meng-Tsung Tsai . 2018 . Optimal Ball Recycling . In Proceedings of the Symposium on Discrete Algorithms (SODA). 2527\u20132546 . Michael A Bender, Jake Christensen, Alex Conway, Mart\u00edn Farach-Colton, Rob Johnson, and Meng-Tsung Tsai. 2018. Optimal Ball Recycling. In Proceedings of the Symposium on Discrete Algorithms (SODA). 2527\u20132546."},{"key":"e_1_3_2_1_15_1","unstructured":"Michael A. Bender S\u00e1ndor P. Fekete Alexander Kr\u00f6ller Vincenzo Liberatore Joseph S. B. Mitchell Valentin Polishchuk and Jukka Suomela. 2015.  Michael A. Bender S\u00e1ndor P. Fekete Alexander Kr\u00f6ller Vincenzo Liberatore Joseph S. B. Mitchell Valentin Polishchuk and Jukka Suomela. 2015."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2015.08.027"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-33475-7_5"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-25870-1_8"},{"key":"e_1_3_2_1_19_1","volume-title":"Woeginger","author":"Chrobak Marek","year":"2001","unstructured":"Marek Chrobak , J\u00e1nos Csirik , Csan\u00e1d Imreh , John Noga , Jir\u00ed Sgall , and Gerhard J . Woeginger . 2001 . Marek Chrobak, J\u00e1nos Csirik, Csan\u00e1d Imreh, John Noga, Jir\u00ed Sgall, and Gerhard J. Woeginger. 2001."},{"key":"e_1_3_2_1_20_1","volume-title":"Buffer Minimization Problem for Multiprocessor Scheduling with Conflicts. In Proceedings of the 28th International Colloquium on Automata, Languages and Programming (ICALP)","volume":"2076","author":"The","unstructured":"The Buffer Minimization Problem for Multiprocessor Scheduling with Conflicts. In Proceedings of the 28th International Colloquium on Automata, Languages and Programming (ICALP) , Vol. 2076 . 862\u2013874. 540- 48224- 5_70 The Buffer Minimization Problem for Multiprocessor Scheduling with Conflicts. In Proceedings of the 28th International Colloquium on Automata, Languages and Programming (ICALP), Vol. 2076. 862\u2013874. 540- 48224- 5_70"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.03.025"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/28395.28434"},{"key":"e_1_3_2_1_23_1","volume-title":"Dietz and Rajeev Raman","author":"Paul","year":"1991","unstructured":"Paul F. Dietz and Rajeev Raman . 1991 . Persistence, Amortization and Randomization. In Proceedings of the Second Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 78\u201388. http:\/\/dl.acm.org\/citation.cfm?id=127787.127809 Paul F. Dietz and Rajeev Raman. 1991. Persistence, Amortization and Randomization. In Proceedings of the Second Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 78\u201388. http:\/\/dl.acm.org\/citation.cfm?id=127787.127809"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-19929-0_14"},{"key":"e_1_3_2_1_25_1","volume-title":"Balanced Scheduling toward Loss-Free Packet Queuing and Delay Fairness. Algorithmica 38, 2 (01","author":"Fleischer Rudolf","year":"2004","unstructured":"Rudolf Fleischer and Hisashi Koga . 2004. Balanced Scheduling toward Loss-Free Packet Queuing and Delay Fairness. Algorithmica 38, 2 (01 Feb 2004 ), 363\u2013376. 003- 1064z Rudolf Fleischer and Hisashi Koga. 2004. Balanced Scheduling toward Loss-Free Packet Queuing and Delay Fairness. Algorithmica 38, 2 (01 Feb 2004), 363\u2013376. 003- 1064z"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-5316(93)90033-Q"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-51963-0_18"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1753171.1753195"},{"key":"e_1_3_2_1_29_1","unstructured":"1753195  1753195"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-03841-4_23"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.79"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1073970.1073982"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-008-9134-x"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.5555\/3118782.3119217"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"crossref","unstructured":"Chung Laung Liu. 1969.  Chung Laung Liu. 1969.","DOI":"10.5465\/ambpp.1969.4980371"},{"key":"e_1_3_2_1_36_1","first-page":"1969","volume-title":"JPL Space Programs Summary","author":"Scheduling","year":"1969","unstructured":"Scheduling algorithms for multiprocessors in a hard real-time environment . JPL Space Programs Summary , 1969 ( 1969 ). Scheduling algorithms for multiprocessors in a hard real-time environment. JPL Space Programs Summary, 1969 (1969)."},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"crossref","unstructured":"Colin McDiarmid. 1989.  Colin McDiarmid. 1989.","DOI":"10.2307\/1445441"},{"key":"e_1_3_2_1_38_1","volume-title":"Surveys in combinatorics 141, 1","author":"On","year":"1989","unstructured":"On the method of bounded differences. Surveys in combinatorics 141, 1 ( 1989 ), 148\u2013188. On the method of bounded differences. Surveys in combinatorics 141, 1 (1989), 148\u2013188."},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.5555\/827271.829072"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.5555\/644108.644210"},{"key":"e_1_3_2_1_41_1","unstructured":"Michael Rosenblum Michel X Goemans and Vahid Tarokh. 2004.  Michael Rosenblum Michel X Goemans and Vahid Tarokh. 2004."},{"key":"e_1_3_2_1_42_1","volume-title":"Twenty-third Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM)","volume":"2","author":"Universal","unstructured":"Universal bounds on buffer size for packetizing fluid policies in input queued, crossbar switches . In Twenty-third Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM) , Vol. 2 . 1126\u20131134. Universal bounds on buffer size for packetizing fluid policies in input queued, crossbar switches. In Twenty-third Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM), Vol. 2. 1126\u20131134."},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/2786.2793"}],"event":{"name":"STOC '19: 51st Annual ACM SIGACT Symposium on the Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Phoenix AZ USA","acronym":"STOC '19"},"container-title":["Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3313276.3316342","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3313276.3316342","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3313276.3316342","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:54:32Z","timestamp":1750204472000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3313276.3316342"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,6,23]]},"references-count":43,"alternative-id":["10.1145\/3313276.3316342","10.1145\/3313276"],"URL":"https:\/\/doi.org\/10.1145\/3313276.3316342","relation":{},"subject":[],"published":{"date-parts":[[2019,6,23]]},"assertion":[{"value":"2019-06-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}