Joseph Mitchell

Abstract:   The Euclidean travelling salesman problem with neighborhoods (TSPN) seeks a shortest path or cycle that visits a given collection of $n$ regions (neighborhoods), $R_1, R_2, ..., 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. We also discuss some problems related to the TSPN, including the watchman route problem (compute a shortest path/cycle that allows a robot to see all of a multiply connected domain) and the relay placement problem for building a connected communication network. Key to some of the results is the $m$-guillotine technique, which gives a tool for obtaining approximation algorithms in many network optimization problems.

Here are some directions to Northeastern University. Lake Hall and Nightingale Hall can be best accessed from the entrance on the corner of Greenleaf Street and Leon Street. The two halls are connected, with no well-defined boundary in between. In particular, 509 Lake Hall is on the same corridor as 544 Nightingale Hall.

There is free parking available for people coming to the Colloquium at Northeastern's visitor parking (Rennaisance Garage). The entrance is from Columbus Avenue. If coming by car, you should park there and take the parking talon. After the lecture, you may pick up the payment coupon from Andrei Zelevinsky.