Geometric TSP on sets

Henk Y. Alkema, Mark T. de Berg

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

Abstract

In One-of-a-Set TSP, also known as the Generalised TSP, the input is a collection P := {P1, ..., Pr} of sets in a metric space and the goal is to compute a minimum-length tour that visits one element from each set. In the Euclidean variant of this problem, each Pi is a set of points in R d that is contained in a given hypercube Hi. We investigate how the complexity of Euclidean One-of-a-Set TSP depends on λ, the ply of the set H := {H1, ..., Hr} of hypercubes (The ply is the smallest λ such that every point in R d is in at most λ of the hypercubes). Furthermore, we show that the problem can be solved in 2 O( λ 1/dn1−1/d) time, where n := Pr i =1 |Pi| is the total number of points. Finally, we show that the problem cannot be solved in 2 o(n ) time when λ = Θ(n), unless the Exponential Time Hypothesis (ETH) fails. In Rectilinear One-of-a-Cube TSP, the input is a set H of hypercubes in R d and the goal is to compute a minimum-length rectilinear tour that visits every hypercube. We show that the problem can be solved in 2 O( λ 1/dn1−1/d log n ) time, where n is the number of hypercubes.

Original languageEnglish
Title of host publication34th International Symposium on Algorithms and Computation, ISAAC 2023
EditorsSatoru Iwata, Naonori Kakimura
PublisherLeibniz-Zentrum für Informatik
Pages6:1-6:19
Number of pages19
ISBN (Electronic)9783959772891
DOIs
Publication statusPublished - Dec 2023
Event34th International Symposium on Algorithms and Computation (ISAAC 2023) - Kyoto, Japan
Duration: 3 Dec 20236 Dec 2023

Publication series

NameLeibniz International Proceedings in Informatics (LIPIcs)
Volume283

Conference

Conference34th International Symposium on Algorithms and Computation (ISAAC 2023)
Country/TerritoryJapan
CityKyoto
Period3/12/236/12/23

Funding

Funding The work in this paper is supported by the Dutch Research Council (NWO) through Gravitation-grant NETWORKS-024.002.003.

FundersFunder number
Nederlandse Organisatie voor Wetenschappelijk OnderzoekNETWORKS-024.002.003

    Keywords

    • Euclidean TSP
    • Rectilinear TSP
    • TSP on Neighbourhoods
    • TSP on Sets

    Fingerprint

    Dive into the research topics of 'Geometric TSP on sets'. Together they form a unique fingerprint.

    Cite this