Suppose we have to deliver heaps of newspapers from various depots
to various locations. How do we route a vehicle of a fixed capacity
to perform such a task efficiently? I will discuss the Chalasani-Motwani-Rao
algorithm for this problem, and will sketch various ideas that can be
used to obtain much better approximation algorithms that run in polynomial
time.
(Joint work with M. Charikar (Stanford) and B. Raghavachari (Dallas).)