Paper Info
Title
Traveling Repairperson, Unrelated Machines, and Other Stories About Average Completion Times
Abstract
We present a unified framework for minimizing average completion time for many seemingly disparate \emph{online} scheduling problems, such as the traveling repairperson problems (TRP), dial-a-ride problems (DARP), and scheduling on unrelated machines. We construct a simple algorithm that handles all these scheduling problems, by computing and later executing auxiliary schedules, each optimizing a certain function on already seen prefix of the input. The optimized function resembles a prize-collecting variant of the original scheduling problem. By a careful analysis of the interplay between these auxiliary schedules, and later employing the resulting inequalities in a factor-revealing linear program, we obtain improved bounds on the competitive ratio for all these scheduling problems. In particular, our techniques yield a $4$-competitive deterministic algorithm for all previously studied variants of online TRP and DARP, and a $3$-competitive one for the scheduling on unrelated machines (also with precedence constraints). This improves over currently best ratios for these problems that are $5.14$ and $4$, respectively. We also show how to use randomization to further reduce the competitive ratios to $1+2/\ln 3 < 2.821$ and $1+1/\ln 2 < 2.443$, respectively. The randomized bounds also substantially improve the current state of the art. Our upper bound for DARP contradicts the lower bound of 3 given by Fink et al. (Inf. Process. Lett. 2009); we pinpoint a flaw in their proof.
Year
DOI
Venue
2021
10.4230/LIPIcs.ICALP.2021.28
ICALP
DocType
Citations 
PageRank 
Conference
0
0.34
References 
Authors
0
3
Name
Order
Citations
PageRank
Marcin Bienkowski101.01
Artur Kraska201.01
Hsiang-Hsuan Liu300.34