Tutte seminar - Chaitanya Swamy

Friday, October 3, 2014 3:30 pm - 3:30 pm EDT (GMT -04:00)

Approximation Algorithms for Vehicle-Routing Problems

Speaker: Chaitanya Swamy
Affiliation: University of Waterloo
Room: Mathematics 3 (M3) 3103

Abstract: 

Vehicle-routing problems (VRPs) constitute a broad class of combinatorial-optimization problems that have been widely studied in both the operations research and computer science literature. Despite this, there remain significant gaps in our understanding of these problems, especially from the perspective of designing efficient algorithms with worst-case approximation guarantees. A fundamental difficulty here stems from our lack of understanding of linear-programming (LP) relaxations for VRPs.

I will describe how to leverage LP-based techniques to successfully tackle two classes of VRPs and obtain strong approximation guarantees for these problems. These are: (a) the classical minimum-latency problem and its multi-vehicle and multi-depot extensions, wherein we seek routes for one or more vehicles that together visit all nodes and minimize the sum of the node-waiting times; and (b) regret-bounded VRPs, wherein regret of a node measures its waiting time relative to its shortest-path distance from the depot, and we seek routes that ensure bounded node regret. Our techniques show how to exploit so-called configuration LPs and bidirected LP-relaxations, which are two classes of LPs that are often believed to be quite powerful (in theory and practice), but have only sporadically been leveraged for vehicle-routing and network-design problems.
The talk will be self-contained.