{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,2]],"date-time":"2026-04-02T21:52:14Z","timestamp":1775166734611,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":30,"publisher":"ACM","license":[{"start":{"date-parts":[[2024,6,10]],"date-time":"2024-06-10T00:00:00Z","timestamp":1717977600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Swedish Research Council","award":["2019-0562"],"award-info":[{"award-number":["2019-0562"]}]},{"name":"Google PhD Fellowship Program","award":[""],"award-info":[{"award-number":[""]}]},{"name":"Swiss State Secretariat for Education, Research and Innovation","award":["MB22.00054"],"award-info":[{"award-number":["MB22.00054"]}]},{"name":"Taub Family Foundation Leader in Science and Technology Fellowship","award":[""],"award-info":[{"award-number":[""]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2024,6,10]]},"DOI":"10.1145\/3618260.3649741","type":"proceedings-article","created":{"date-parts":[[2024,6,11]],"date-time":"2024-06-11T19:25:02Z","timestamp":1718133902000},"page":"36-46","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["Online Edge Coloring Is (Nearly) as Easy as Offline"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0009-0004-0874-2356","authenticated-orcid":false,"given":"Joakim","family":"Blikstad","sequence":"first","affiliation":[{"name":"KTH Royal Institute of Technology, Stockholm, Sweden \/ Max Planck Institute for Informatics, Saarbr\u00fccken, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2997-1372","authenticated-orcid":false,"given":"Ola","family":"Svensson","sequence":"additional","affiliation":[{"name":"EPFL, Lausanne, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0000-6713-7253","authenticated-orcid":false,"given":"Radu","family":"Vintan","sequence":"additional","affiliation":[{"name":"EPFL, Lausanne, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1896-2948","authenticated-orcid":false,"given":"David","family":"Wajc","sequence":"additional","affiliation":[{"name":"Technion - Israel Institute of Technology, Haifa, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,6,11]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973082.95"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2003.1238223"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2012.v008a025"},{"key":"e_1_3_2_1_4_1","series-title":"SIAM J. Comput., 48","volume-title":"An Algorithm for Koml\u00f3s Conjecture Matching Banaszczyk\u2019s bound","author":"Bansal Nikhil","year":"2016","unstructured":"Nikhil Bansal, Daniel Dadush, and Shashwat Garg. 2016. An Algorithm for Koml\u00f3s Conjecture Matching Banaszczyk\u2019s bound. SIAM J. Comput., 48 (2016)."},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(92)90209-E"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01294260"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976465.168"},{"key":"e_1_3_2_1_8_1","volume-title":"Proceedings of the 62nd Symposium on Foundations of Computer Science (FOCS). 1277\u20131284","author":"Blanc Guy","year":"2021","unstructured":"Guy Blanc and Moses Charikar. 2021. Multiway Online Correlated Selection. In Proceedings of the 62nd Symposium on Foundations of Computer Science (FOCS). 1277\u20131284."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"crossref","unstructured":"Joakim Blikstad Ola Svensson Radu Vintan and David Wajc. 2024. Online Edge Coloring is (Nearly) as Easy as Offline. arxiv:2402.18339.","DOI":"10.1145\/3618260.3649741"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977936.30"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585105"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00010"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.62"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00046"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176996452"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00011"},{"key":"e_1_3_2_1_17_1","volume-title":"Proceedings of the 62nd Symposium on Foundations of Computer Science (FOCS). 1265\u20131276","author":"Gao Ruiquan","year":"2021","unstructured":"Ruiquan Gao, Zhongtian He, Zhiyi Huang, Zipei Nie, Bijun Yuan, and Yan Zhong. 2021. Improved Online Correlated Selection. In Proceedings of the 62nd Symposium on Foundations of Computer Science (FOCS). 1265\u20131276."},{"key":"e_1_3_2_1_18_1","volume-title":"Probabilistic methods for algorithmic discrete mathematics. 16","author":"Habib Michel","unstructured":"Michel Habib, Colin McDiarmid, Jorge Ramirez-Alfonsin, and Bruce Reed. 1998. Probabilistic methods for algorithmic discrete mathematics. 16, Springer Science & Business Media."},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3390890"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00130"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00133"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcta.1996.0001"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/100216.100262"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3519986"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1284320.1284321"},{"key":"e_1_3_2_1_26_1","unstructured":"Joseph (Seffi) Naor Aravind Srinivasan and David Wajc. 2023. Online Dependent Rounding Schemes. arXiv preprint arXiv:2301.08680."},{"key":"e_1_3_2_1_27_1","first-page":"1","article-title":"The Greedy Algorithm is not Optimal for On-Line Edge Coloring. In Proceedings of the 48th International Colloquium on Automata","volume":"109","author":"Saberi Amin","year":"2021","unstructured":"Amin Saberi and David Wajc. 2021. The Greedy Algorithm is not Optimal for On-Line Edge Coloring. In Proceedings of the 48th International Colloquium on Automata, Languages and Programming (ICALP). 109:1\u2013109:18.","journal-title":"Languages and Programming (ICALP)."},{"key":"e_1_3_2_1_28_1","volume-title":"On an estimate of the chromatic class of a p-graph. Diskret analiz, 3","author":"Vizing Vadim G","year":"1964","unstructured":"Vadim G Vizing. 1964. On an estimate of the chromatic class of a p-graph. Diskret analiz, 3 (1964), 25\u201330."},{"key":"e_1_3_2_1_29_1","first-page":"3","article-title":"Vertex colorings with given colors","volume":"29","author":"Vizing Vadim G","year":"1976","unstructured":"Vadim G Vizing. 1976. Vertex colorings with given colors. Diskret. Analiz, 29 (1976), 3\u201310.","journal-title":"Diskret. Analiz"},{"key":"e_1_3_2_1_30_1","volume-title":"Matching Theory Under Uncertainty. Ph. D. Dissertation","author":"Wajc David","unstructured":"David Wajc. 2020. Matching Theory Under Uncertainty. Ph. D. Dissertation. Carnegie Mellon University."}],"event":{"name":"STOC '24: 56th Annual ACM Symposium on Theory of Computing","location":"Vancouver BC Canada","acronym":"STOC '24","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 56th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3618260.3649741","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3618260.3649741","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T00:03:52Z","timestamp":1750291432000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3618260.3649741"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6,10]]},"references-count":30,"alternative-id":["10.1145\/3618260.3649741","10.1145\/3618260"],"URL":"https:\/\/doi.org\/10.1145\/3618260.3649741","relation":{},"subject":[],"published":{"date-parts":[[2024,6,10]]},"assertion":[{"value":"2024-06-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}