ONLINE EDGE COLORING VIA TREE RECURRENCES AND CORRELATION DECAY\ast

作     者：Kulkarni, Janardhan Liu, Yang p. Sah, Ashwin Sawhney, Mehtaab s. Tarnawski, Jakub 

作者机构：Microsoft Res Redmond WA 98052 USA Stanford Univ Dept Math Stanford CA 94305 USA MIT Cambridge MA 02139 USA MIT Commack NY 11725 USA 

出 版 物：《SIAM JOURNAL ON COMPUTING》 (SIAM J Comput)

年 卷 期：2024年第53卷第1期

页      面：87-110页

核心收录：

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：Department of Defense (DoD) through the National Defense Science and Engineering Graduate Fellowship NSF Graduate Research Fellowship Program [DGE-676 1745302] 

主　　题：edge coloring online algorithms tree recurrences correlation decay Redmond. 

摘      要：We give an online algorithm that with high probability computes a ( e e - 1 + o(1))\Delta edge coloring on a graph G with maximum degree \Delta = \omega(logn) under online edge arrivals against oblivious adversaries, making first progress on the conjecture of Bar -Noy, Motwani, and Naor in this general setting. Our algorithm is based on reducing to a matching problem on locally treelike graphs, and then applying a tree recurrence based approach for arguing correlation decay.