1 citations · 2 across the 10 of their papers we have counts for
5 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…
Correlation Clustering with Random Partial Information
Rajath Rao K. N., Jens Schlöter, Sami Davies +2
Correlation clustering is a fundamental unsupervised learning problem. On complete graphs, both the min-disagreement and min-max objectives admit constant-factor approximations, ye…
Improved Lower Bounds and Output Augmentation for Facility Location Mechanisms
Rafael Gomes, Sophie Klumper, Guido Schäfer +1
We study the strategic facility location problem under the egalitarian objective, where a mechanism uses the reported locations of a set of agents in Euclidean space to select a fa…
Online Scheduling with a Stochastic Signal
Romain Cosson, Jingwei Li, Alexander Lindermayr +1
Nonclairvoyant scheduling is a fundamental online model in which processing times are initially unknown to the scheduler. Unfortunately, for important objectives such as total comp…
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],…