Everyone is welcome to attend the lecture of David Wajc (CMU)
Title: The Greedy Algorithm is *Not* Optimal for On-line Edge Coloring
Abstract: The classic edge coloring problem is the problem of partitioning the edges of a graph into matchings, ideally few in number. This problem has multiple applications in myriad scheduling problems. In this talk I will discuss this problem in the online adversarial vertex arrival model of Karp, Vazirani and Vazirani. Under such adversarial arrivals, a 1992 paper of Bar-Noy et al., titled ‘’The greedy algorithm is optimal for on-line edge coloring’’, proves the optimality of the trivial greedy algorithm, which requires 2Delta-1 colors on graphs with maximum degree Delta. In contrast, by Vizing's Theorem any graph can be edge colored (offline) using Delta+1 colors. However, the online lower bound of Bar-Noy et al. requires Delta=O(polylog n), and they conjectured the existence of better algorithms
than greedy for Delta large enough. In this talk I will discuss our positive resolution of this conjecture for bipartite graphs and present our optimal algorithms (up to o(1) terms) for such graphs. Along the way, we find a surprising dichotomy between the known and unknown Delta scenario.
Joint work with Ilan Reuven Cohen and Binghui Peng.
