MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Elbassioni, Khaled M.
Fishkin, Aleksei V.
Sitters, Rene		dblp
dblp
dblp
Not MPG Author(s):
Fishkin, Aleksei V.
Editor(s):
Asano, Tetsuodblp
Not MPII Editor(s):
Asano, Tetsuo
BibTeX cite key*:
Elbassioni2006g
Title, Booktitle
Title*:
On Approximating the TSP with Intersecting Neighborhoods
Booktitle*:
Algorithms and Computation : 17th International Symposium, ISAAC 2006
Event, URLs
Conference URL::
Downloading URL:
http://www.springerlink.com/content/w511640r888k4852/fulltext.pdf
Event Address*:
Kolkata, India
Language:
English
Event Date*
(no longer used):
Organization:
Event Start Date:
18 December 2006
Event End Date:
20 December 2006
Publisher
Name*:
Springer
URL:
http://www.springer.com/
Address*:
Berlin, Germany
Type:
Vol, No, Year, pp.
Series:
Lecture Notes in Computer Science
Volume:
4288
Number:
Month:
Pages:
213-222
Year*:
2006
VG Wort Pages:
ISBN/ISSN:
3-540-49694-6
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) 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.
URL for the Abstract:
http://www.springerlink.com/content/w511640r888k4852/
Download
Access Level:
Public

Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Algorithms and Complexity Group
Appearance:
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{Elbassioni2006g,
AUTHOR = {Elbassioni, Khaled M. and Fishkin, Aleksei V. and Sitters, Rene},
 EDITOR = {Asano, Tetsuo},
 TITLE = {On Approximating the {TSP} with Intersecting Neighborhoods},
 BOOKTITLE = {Algorithms and Computation : 17th International Symposium, ISAAC 2006},
 PUBLISHER = {Springer},
 YEAR = {2006},
 VOLUME = {4288},
 PAGES = {213--222},
 SERIES = {Lecture Notes in Computer Science},
 ADDRESS = {Kolkata, India},
 ISBN = {3-540-49694-6},
}

Entry last modified by Anja Becker, 03/02/2010
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Khaled Elbassioni		Created
12/27/2006 11:20:08 PM
Revisions
7.
6.
5.
4.
3.		Editor(s)
Anja Becker
Christine Kiesel
Uwe Brahm
Regina Kraemer
Regina Kraemer		Edit Dates
25.02.2008 09:08:54
02.05.2007 15:29:40
04/25/2007 10:28:41 AM
04/11/2007 11:09:28 AM
09.03.2007 10:46:54