On the FirstFit Algorithm for Online Unit-Interval Coloring

10^th November 2025, 14:00 Ashton Lecture Theatre
Bob Krekelberg
Utrecht

Abstract

In this paper, we analyze FirstFit on online unit-length intervals, which can either be open or closed, further investigating FirstFit's true performance. We develop a sophisticated counting method by generalizing the classic neighborhood bound, which limits the color FirstFit can assign an interval by counting the potential intersections. In the generalization, we show that for any interval, there is a critical interval intersecting it that can help reduce overestimation of the number of intersections, and it further helps bound the color an interval can be assigned. The technical challenge lies in reliably finding these critical intervals. Using this new technique, we provide a tight analysis showing that FirstFit uses at most 2ω colors when all endpoints are integral, and an upper bound of ⌈(7/3)ω⌉ − 2 in the general case of open and closed unit intervals, where ω denotes the optimal number of colors needed.