Linear-Programming based Approximation Algorithms for Multi-Vehicle Minimum Latency Problems

Ian Post, Chaitanya Swamy

We consider various {\em multi-vehicle versions of the minimum latency problem}. There is a fleet of $k$ vehicles located at one or more depot nodes, and we seek a collection of ro…