N&O seminar: David Wajc (CMU)

Everyone is welcome to attend the public lecture of David, title 'The Greedy Algorithm is *Not* Optimal for On-line Edge Coloring'
  • What Networks & Optimization English
  • When 19-10-2018 from 14:00 to 15:00 (Europe/Amsterdam / UTC200)
  • Where Room L016 at CWI, Science Park 123 in Amsterdam
  • Contact Name Daniel Dadush
  • Web Visit external website
  • Add event to calendar iCal

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.