Approximation Algorithms for TSP with Neighborhoods and Related Geometric Network Optimization Problems

Joe Mitchell
Department of Applied Mathematics and Statistics
SUNY, Stony Brook


Tuesday, May 31, 2011
4:30 - 5:30 PM
Huang 4

Abstract:

The Euclidean travelling salesman problem with neighborhoods (TSPN) seeks a shortest path or cycle that visits a given collection of $n$ regions ({\em neighborhoods}), $R_1, R_2,\ldots,R_n$. The TSPN is a generalization of the classic TSP (when $R_i$ are points) that arises in several other related geometric optimization problems. We present methods that yield provable approximation guarantees for the TSPN in the plane, including a constant-factor approximation algorithm for the general case of connected regions. We also discuss some problems related to the TSPN, including the {\em watchman route problem}: compute a shortest path/cycle that allows a robot to see all of a given geometric domain.

---

Operations Research Colloquia: http://or.stanford.edu/oras_seminars.html