10 papers
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…
Optimal Verification of a Minimum-Weight Basis in an Uncertainty Matroid
Haya Diwan, Lisa Hellerstein, Nicole Megow +1
Research in explorable uncertainty addresses combinatorial optimization problems where there is partial information about the values of numeric input parameters, and exact values o…
Delayed-Clairvoyant Flow Time Scheduling via a Borrow Graph Analysis
Alexander Lindermayr, Jens Schlöter
We study the problem of preemptively scheduling jobs online over time on a single machine to minimize the total flow time. In the traditional clairvoyant scheduling model, the sche…
Online Flow Time Minimization with Gradually Revealed Jobs
Alexander Lindermayr, Guido Schäfer, Jens Schlöter +1
We consider the problem of online preemptive scheduling on a single machine to minimize the total flow time. In clairvoyant scheduling, where job processing times are revealed upon…
Non-Clairvoyant Scheduling with Progress Bars
Ziyad Benomar, Romain Cosson, Alexander Lindermayr +1
In non-clairvoyant scheduling, the goal is to minimize the total job completion time without prior knowledge of individual job processing times. This classical online optimization…