Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:








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, Tetsuo

dblp

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

URL of the conference:


URL for downloading the paper:

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
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
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
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section