2 papers
cs.DM2026
A Primal-Dual Approach to Randomized Online Bidding with Tail Constraints
Royce Kraakman, Bob Krekelberg, Alison Hsiang-Hsuan Liu +1
Controlling tail risk in randomized algorithms has received increasing attention. Randomized online algorithms can achieve a lower expected competitive ratio than the competitive r…
cs.DM2025
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,…