Karin Saoub

Being Greedy with Crayons
Abstract: Graph coloring has been studied in various forms for over a century. From the famous Four Color Theorem, which has implications in map design, to Dynamic Storage Allocation, which can aid in computer design, graph coloring has been important partially due to its wide variety of applications. This talk will focus on the First-Fit algorithm, an online algorithm that views and colors vertices one at a time, rather than using the structure of the entire graph to find a proper coloring. We will consider situations where First-Fit provides good colorings, those where it fails, and how we determine the difference. Finally, we will discuss a few applications of online algorithms, specifically scheduling problems and Dynamic Storage Allocation.