# Item

ITEM ACTIONSEXPORT

Released

Conference Paper

#### On Approximating the TSP with Intersecting Neighborhoods

##### MPS-Authors

##### Locator

There are no locators available

##### Fulltext (public)

There are no public fulltexts available

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Elbassioni, K., Fishkin, A. V., & Sitters, R. (2006). On Approximating the TSP
with Intersecting Neighborhoods. In *Algorithms and Computation: 17th International Symposium, ISAAC
2006* (pp. 213-222). Berlin, Germany: Springer.

Cite as: http://hdl.handle.net/11858/00-001M-0000-000F-2391-E

##### 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: We give the first $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. The proof follows from two packing lemmas that are of
independent interest.
For the problem in its most general form (but without the specified points
restriction) we give a simple $O(\log n)$-approximation algorithm.