Campus Event Calendar
Event Entry
What and Who
On approximating the TSP with intersecting neighborhoods
Khaled Elbassioni
Max-Planck-Institut für Informatik - D1
AG1 Mittagsseminar (own work)
AG 1, AG 3, AG 5, RG2, AG 2, AG 4, RG1, SWS
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Tuesday, 6 February 2007
13:30
30 Minutes
E1 4
024
Saarbrücken
Abstract
In the TSP with neighborhoods problem we are given a set of $n$ regions (neighborhoods) in the plane, and seek to find a minimum length TSP tour that goes through all the regions. We give two approximation algorithms for the case when the regions are allowed to intersect: (I) an $O(1)$-factor approximation algorithm for intersecting convex fat objects of comparable diameters where we are allowed to hit each object only at a finite set of specified points.
(II) For the problem in its most general form (but without the specified points restriction) we give a simple $O(\log n)$-approximation algorithm.
Joint work with Aleksei V. Fishkin and Rene Sitters.
Contact
Khaled Elbassioni
--email hidden
passcode not visible
logged in users only
Khaled Elbassioni, 02/02/2007 19:15 -- Created document.