On the minimum latency problem
<|reference_start|>On the minimum latency problem: We are given a set of points $p_1,\ldots , p_n$ and a symmetric distance matrix $(d_{ij})$ giving the distance between $p_i$ and $p_j$. We wish to construct a tour that minimizes $\sum_{i=1}^n \ell(i)$, where $\ell(i)$ is the {\em latency} of $p_i$, defined to be the distance traveled before first visiting $p_i$. This problem is also known in the literature as the {\em deliveryman problem} or the {\em traveling repairman problem}. It arises in a number of applications including disk-head scheduling, and turns out to be surprisingly different from the traveling salesman problem in character. We give exact and approximate solutions to a number of cases, including a constant-factor approximation algorithm whenever the distance matrix satisfies the triangle inequality.<|reference_end|>
@article{blum1994on,
    title={On the minimum latency problem},
    author={Avrim Blum, Prasad Chalasani, Don Coppersmith, Bill Pulleyblank,
  Prabhakar Raghavan, Madhu Sudan},
    journal={arXiv preprint arXiv:math/9409223},
    year={1994},
    number={LACES 68Q-94-18},
    archivePrefix={arXiv},
    eprint={math/9409223},
    primaryClass={math.CO cs.CC}
}