4 papers · 1 filter
Better Late Than Never: Online Flow Time Scheduling with Online Estimates
Anupam Gupta, Haim Kaplan, Alexander Lindermayr +2
In the classical online flow-time scheduling problem on a single machine, jobs arrive over time and must be processed to minimize the total time they spend in the system: for over…
A Simpler Analysis for -Clairvoyant Flow Time Scheduling
Anupam Gupta, Haim Kaplan, Alexander Lindermayr +2
We simplify the proof of the optimality of the Shortest Lower-Bound First (SLF) algorithm, introduced by Gupta, Kaplan, Lindermayr, Schlöter, and Yingchareonthawornchai [FOCS'25],…
The Online Submodular Cover Problem
Anupam Gupta, Roie Levin
In the submodular cover problem, we are given a monotone submodular function , and we want to pick the min-cost set such that . Motivated by problems in network…
Pairwise-Independent Contention Resolution
Anupam Gupta, Jinqiao Hu, Gregory Kehne +1
We study online contention resolution schemes (OCRSs) and prophet inequalities for non-product distributions. Specifically, when the active set is sampled according to a pairwise-i…