3 papers
cs.DM2026
The Power of Amortization on Minimizing Total Completion Time with Explorable Uncertainty
Bob Krekelberg, Alison Hsiang-Hsuan Liu, Fu-Hong Liu +2
We study online scheduling to minimize total completion time with explorable uncertainty on single and multiple machines. Each job comes with an upper limit of its processing time,…
cs.DS2026
Online Firefighting on Cactus Graphs
Max Hugen, Bob Krekelberg, Alison Hsiang-Hsuan Liu
It is known that the online firefighting is 2-competitive on trees (Coupechoux et al. 2019), which suggests that the problem is relatively easy on trees. We extend the study to gra…
cs.DS2025
On the FirstFit Algorithm for Online Unit-Interval Coloring
Bob Krekelberg, Alison Hsiang-Hsuan Liu
In this paper, we study the performance of the FirstFit algorithm for the online unit-length intervals coloring problem where the intervals can be either open or closed, which serv…