TY - GEN

T1 - Geometric TSP on sets

AU - Alkema, Henk Y.

AU - de Berg, Mark T.

PY - 2023/12

Y1 - 2023/12

N2 - 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.

AB - 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.

KW - Euclidean TSP

KW - Rectilinear TSP

KW - TSP on Neighbourhoods

KW - TSP on Sets

UR - http://www.scopus.com/inward/record.url?scp=85179121617&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.ISAAC.2023.6

DO - 10.4230/LIPIcs.ISAAC.2023.6

M3 - Conference contribution

T3 - Leibniz International Proceedings in Informatics (LIPIcs)

SP - 6:1-6:19

BT - 34th International Symposium on Algorithms and Computation, ISAAC 2023

A2 - Iwata, Satoru

A2 - Kakimura, Naonori

PB - Leibniz-Zentrum für Informatik

T2 - 34th International Symposium on Algorithms and Computation (ISAAC 2023)

Y2 - 3 December 2023 through 6 December 2023

ER -