# Traveling Repairperson, Unrelated Machines, and Other Stories About Average Completion Times

arXiv: https://arxiv.org/abs/2102.06904 · HTML: https://mlsanity.com/paper/2102.06904/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Feb 2021.

## Built on by (most cited first, 3 of 3)

- [Permutation Predictions for Non-Clairvoyant Scheduling](https://mlsanity.com/paper/2202.10199/) (2022)
- [Minimalistic Predictions to Schedule Jobs with Online Precedence Constraints](https://mlsanity.com/paper/2301.12863/) (2023)
- [Speed-Oblivious Online Scheduling: Knowing (Precise) Speeds is not Necessary](https://mlsanity.com/paper/2302.00985/) (2023)

## Abstract (arXiv)

We present a unified framework for minimizing average completion time for many seemingly disparate 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.