BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260408T223340Z
UID:Seminar-dept-1299@lxserverA.csc.liv.ac.uk.csc.liv.ac.uk
ORGANIZER:CN=Lutz Oettershagen:MAILTO:Lutz.Oettershagen@liverpool.ac.uk
DTSTART:20251110T140000
DTEND:20251110T150000
SUMMARY:School Seminar Series
DESCRIPTION:Bob Krekelberg: On the FirstFit Algorithm for Online Unit-Interval Coloring\n\nIn 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.\n\n\n\nThere 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.\n\n\n\nCounting 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.\n\nTo address this, we introduce the Pivot Bound, a generalization of the neighborhood bound that more accurately captures the structure of the problem.\n\n\n\nUsing 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.\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=1299
LOCATION:Ashton Lecture Theatre
END:VEVENT
END:VCALENDAR