English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
 
 
DownloadE-Mail
 Local TagsRelease HistoryDetailsSummary
  On Approximating the TSP with Intersecting Neighborhoods

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.

Item is

 

show all hide all

Basic

show hide
Item Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-2391-E Version Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-2393-A
Genre: Conference Paper

Files

show Files

Locators

show

Creators

show
hide
 Creators:
Elbassioni, Khaled1, Author           
Fishkin, Aleksei V.1, Author           
Sitters, Rene1, Author           
Asano, Tetsuo1, Editor           
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Content

show
hide
Free keywords: -
 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.

Details

show
hide
Language(s): eng - English
 Dates: 2007-04-252006
 Publication Status: Issued
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: eDoc: 314618
Other: Local-ID: C1256428004B93B8-A6FE9C8693113897C1257251007AB1AD-Elbassioni2006g
 Degree: -

Event

show
hide
Title: Untitled Event
Place of Event: Kolkata, India
Start-/End Date: 2006-12-18

Legal Case

show

Project information

show

Source 1

show
hide
Title: Algorithms and Computation : 17th International Symposium, ISAAC 2006
Source Genre: Proceedings
 Creator(s):
Affiliations:
Publ. Info: Berlin, Germany : Springer
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 213 - 222 Identifier: ISBN: 978-3-540-49694-6

Source 2

show
hide
Title: Lecture Notes in Computer Science
Source Genre: Series
 Creator(s):
Affiliations:
Publ. Info: -
Pages: - Volume / Issue: 4288 Sequence Number: - Start / End Page: - Identifier: -