Die Dozenten der Informatik-Institute der Technischen Universität Braunschweig laden im Rahmen des Informatik-Kolloquiums zu folgendem Vortrag ein:
Joe Mitchell, Stony Brook University, NY, USA: Approximation Algorithms for TSP with Neighborhoods and Related Geometric Network Optimization Problems
Beginn: 10.06.2011, 11:30 Uhr Ort: TU Braunschweig, Informatikzentrum, Mühlenpfordtstraße 23, 1. OG, Hörsaal M 160 Webseite: http://www.ibr.cs.tu-bs.de/cal/kolloq/2011-06-10-mitchell.html Kontakt: Prof. Dr. Sándor Fekete
The Euclidean travelling salesman problem with neighborhoods (TSPN) seeks a shortest path or cycle that visits a given collection of n regions ("neighborhoods"), R1, R2,..,Rn. The TSPN is a generalization of the classic TSP (when Ri 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 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.