How to Route Vehicles in the Plane, in Theory

ABSTRACT: Although famously NP-hard (non-deterministic
polynomial-time hard), the traveling salesman problem, an old
DIMACS (Center for Discrete Mathematics and Theoretical
Computer Science) implementation challenge, can be solved
near-optimally in most real-life instances. This was partially
explained by Arora and by Mitchell who designed algorithms with
arbitrarily good accuracy when the cities can be viewed as
points in the plane. This breakthrough rested on a simple
paradigm that was later used for many other optimization
problems in geometric settings. Most recently, it has come into
play in the design of an algorithm for a version of the vehicle
routing problem. In this problem, a depot contains goods to be
delivered to customers, but the delivery truck only has enough
capacities to serve k customers at a time and must go back to
the depot to refill the truck. This talk outlines a
quasi-polynomial time approximation scheme for this problem,
and discusses possible extensions. This is joint work with
Aparna Das.


BIO: After a PhD and initial career in France, Claire Mathieu
has been at Brown University since 2004. Her interests span the
design and analysis of algorithms, with a particular interest
in probabilistic techniques for approximation algorithms. She
has worked on bin packing, scheduling, clustering, rank
aggregation, and other optimization problems. She is a frequent
visitor of the Theory Group at MSR.