Approximation Algorithms for Traveling Salesman Problem with Neighborhoods and Related Geometric Network Optimization Problems


Joseph Mitchell

Stony Brook

Northeastern University

Thursday, February 24, 2011


Talk at 4:30 p.m. in 509 Lake Hall

Tea at 4:00 p.m. in 544 Nightingale Hall


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.

Home Web page:  Alexandru I. Suciu  Comments to:  
Posted:: January 13, 2011    URL: