  Given a set of clients with demands, the Capacitated Vehicle Routing problem
is to find a set of tours that collectively cover all client demand, such that
the capacity of each vehicle is not exceeded and such that the sum of the tour
lengths is minimized. In this paper, we provide a 4/3-approximation algorithm
for Capacitated Vehicle Routing on trees, improving over the previous
best-known approximation ratio of $(\sqrt{41}-1)/4$ by Asano et al., while
using the same lower bound. Asano et al. show that there exist instances whose
optimal cost is 4/3 times this lower bound. Notably, our 4/3 approximation
ratio is therefore tight for this lower bound, achieving the best-possible
performance.

Data Structures and Algorithms