On the FirstFit Algorithm for Online Unit-Interval Coloring

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

Abstract

In this talk we take a look at the FirstFit algorithm for online coloring of unit-length intervals, which can either be open or closed. In the online interval coloring problem, intervals arrive sequentially, and upon each arrival, the algorithm must assign a color immediately and irrevocably, ensuring that overlapping intervals receive distinct colors.

There is a long line of research on the FirstFit algorithm for online coloring of intervals. For general intervals, however, a gap remains between the best known upper and lower bounds on its performance. By focusing on unit-length intervals, we aim to gain deeper insight into the behavior of FirstFit and contribute toward closing this gap.

Counting arguments are commonly used to analyze the performance of FirstFit; however, the challenge lies in determining which intervals should contribute to the upper bound on the color assigned to a given interval. A standard approach is the neighborhood bound, which limits the color of an interval by the number of intervals intersecting it. In the setting of open and closed unit intervals, however, this bound tends to overcount intersections.
To address this, we introduce the Pivot Bound, a generalization of the neighborhood bound that more accurately captures the structure of the problem.

Using this new technique, we give a tight analysis showing that FirstFit uses at most 2ω colors when all endpoints are integral, and at most ⌈(7/3)ω⌉ − 2 in the general case of open and closed unit intervals, where ω denotes the optimal number of colors required.

Biography

Bob is a PhD-student in the Algorithms and Complexity group of Utrecht University. His research involves online algorithms and explorable uncertainty.