  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 routes for these vehicles that visit all nodes so
as to minimize the total latency incurred, which is the sum of the client
waiting times. We obtain an $8.497$-approximation for the version where
vehicles may be located at multiple depots and a $7.183$-approximation for the
version where all vehicles are located at the same depot, both of which are the
first improvements on this problem in a decade. Perhaps more significantly, our
algorithms exploit various LP-relaxations for minimum-latency problems. We show
how to effectively leverage two classes of LPs---{\em configuration LPs} and
{\em bidirected LP-relaxations}---that are often believed to be quite powerful
but have only sporadically been effectively leveraged for network-design and
vehicle-routing problems. This gives the first concrete evidence of the
effectiveness of LP-relaxations for this class of problems. The
$8.497$-approximation the multiple-depot version is obtained by rounding a
near-optimal solution to an underlying configuration LP for the problem. The
$7.183$-approximation can be obtained both via rounding a bidirected LP for the
single-depot problem or via more combinatorial means. The latter approach uses
a bidirected LP to obtain the following key result that is of independent
interest: for any $k$, we can efficiently compute a rooted tree that is at
least as good, with respect to the prize-collecting objective (i.e., edge cost
+ number of uncovered nodes) as the best collection of $k$ rooted paths. Our
algorithms are versatile and extend easily to handle various extensions
involving: (i) weighted sum of latencies, (ii) constraints specifying which
depots may serve which nodes, (iii) node service times.
