The minimum latency tour problem (MLT), also known as the traveling repairman problem, is a variant of the Traveling Salesperson Problem (TSP) in which the starting node of the tour is given and the goal is to minimize the sum of the arrival times at the other nodes. This problem has been studied a lot by the Operations Research community since it arises in many situations like vehicle routing, network design etc. Since it is NP-complete for general metrics, researchers have come up with approximation algorithms that produce solutions *provably* within some factor from the optimum. Karakostas presents a quasipolynomial-time approximation scheme for this problem when the instance is a weighted tree and when the the nodes lie in the Euclidean space of dimension d for a fixed d. In order to do this, he proves a somewhat surprising connection between the MLT and the TSP. This is joint work with Prof. Sanjeev Arora.

*If time permits, Karakostas will also discuss different assumptions the systems research community makes about web traffic (e.g. the distribution of a typical page request trace) and how one can exploit them. This work is still in-progress with Prof's Dimitris Serpanos and Wayne Wolf.