Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT
 
 
DownloadE-Mail
 Lokale TagsFreigabegeschichteDetailsÜbersicht
  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

 

einblenden: alle ausblenden: alle

Basisdaten

einblenden: ausblenden:
Datensatz-Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-2391-E Versions-Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-2393-A
Genre: Konferenzbeitrag

Externe Referenzen

einblenden:

Urheber

einblenden:
ausblenden:
 Urheber:
Elbassioni, Khaled1, Autor           
Fishkin, Aleksei V.1, Autor           
Sitters, Rene1, Autor           
Asano, Tetsuo1, Herausgeber           
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Inhalt

einblenden:
ausblenden:
Schlagwörter: -
 Zusammenfassung: 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

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 2007-04-252006
 Publikationsstatus: Erschienen
 Seiten: -
 Ort, Verlag, Ausgabe: -
 Inhaltsverzeichnis: -
 Art der Begutachtung: -
 Identifikatoren: eDoc: 314618
Anderer: Local-ID: C1256428004B93B8-A6FE9C8693113897C1257251007AB1AD-Elbassioni2006g
 Art des Abschluß: -

Veranstaltung

einblenden:
ausblenden:
Titel: Untitled Event
Veranstaltungsort: Kolkata, India
Start-/Enddatum: 2006-12-18

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle 1

einblenden:
ausblenden:
Titel: Algorithms and Computation : 17th International Symposium, ISAAC 2006
Genre der Quelle: Konferenzband
 Urheber:
Affiliations:
Ort, Verlag, Ausgabe: Berlin, Germany : Springer
Seiten: - Band / Heft: - Artikelnummer: - Start- / Endseite: 213 - 222 Identifikator: ISBN: 978-3-540-49694-6

Quelle 2

einblenden:
ausblenden:
Titel: Lecture Notes in Computer Science
Genre der Quelle: Reihe
 Urheber:
Affiliations:
Ort, Verlag, Ausgabe: -
Seiten: - Band / Heft: 4288 Artikelnummer: - Start- / Endseite: - Identifikator: -