2 papers
cs.DS2021
Traveling Repairperson, Unrelated Machines, and Other Stories About Average Completion Times
Marcin Bienkowski, Artur Kraska, Hsiang-Hsuan Liu
We present a unified framework for minimizing average completion time for many seemingly disparate online scheduling problems, such as the traveling repairperson problems (TRP), di…
cs.DS2018
A Primal-Dual Online Deterministic Algorithm for Matching with Delays
Marcin Bienkowski, Artur Kraska, Hsiang-Hsuan Liu +1
In the Min-cost Perfect Matching with Delays (MPMD) problem, 2 m requests arrive over time at points of a metric space. An online algorithm has to connect these requests in pairs,…