# Faster Approximation Schemes for k-TSP and k-MST in the Euclidean Space

Ernest van Wijland, Hang Zhou

► To cite this version:

Ernest van Wijland, Hang Zhou. Faster Approximation Schemes for k-TSP and k-MST in the Euclidean Space. International Symposium on Computational Geometry (SoCG), 2024, Athens, Greece. hal-04482962

HAL Id: hal-04482962

https://hal.science/hal-04482962v1

Submitted on 28 Feb 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# Faster Approximation Schemes for *k*-TSP and *k*-MST
in the Euclidean Space

Ernest van Wijland*

Hang Zhou†

## Abstract

In the Euclidean *k*-TSP (resp. Euclidean *k*-MST), we are given *n* points in the *d*-dimensional Euclidean space (for any fixed constant *d* ≥ 2) and a positive integer *k*, the goal is to find a shortest tour visiting at least *k* points (resp. a minimum tree spanning at least *k* points).

We give approximation schemes for both Euclidean *k*-TSP and Euclidean *k*-MST in time $2^{O(1/\epsilon^{d-1})} \cdot n \cdot (\log n)^{d \cdot 4^d}$. This improves the running time of the previous approximation schemes due to Arora [J. ACM 1998] and Mitchell [SICOMP 1999]. Our algorithms can be derandomized by increasing the running time by a factor $O(n^d)$. In addition, our algorithm for Euclidean *k*-TSP is Gap-ETH tight, given the matching Gap-ETH lower bound due to Kisfaludi-Bak, Nederlof, and Węgrzycki [FOCS 2021].

<footnote>* École Normale Supérieure de Paris, France.</footnote>

<footnote>† École Polytechnique, IP Paris, France.</footnote>
# 1 Introduction

We study two problems in the Euclidean space. We are given a set of $n$ points in $\mathbb{R}^d$ and an integer $k \in [2, n]$. In the *Euclidean k-traveling salesman problem* (Euclidean k-TSP), we look for a shortest tour visiting at least $k$ points. In the *Euclidean k-minimum spanning tree problem* (Euclidean k-MST), we look for a minimum tree spanning at least $k$ points.

Both Euclidean k-TSP and Euclidean k-MST are NP-hard [GGJ76, FHJM94]. Approximation algorithms for both problems have been studied extensively, e.g., [Aro98, MM95, Mit99, MBCV98, BCV95, Epp97, GH94, RSM$^+$96, FHJM94]. The best-to-date approximation algorithms are due to the Gödel-prize-winning approximation schemes<fnref n="1" /> of Arora [Aro98] and Mitchell [Mit99], which are among the most prominent results in combinatorial optimization. The approximation schemes of Arora [Aro98] for both problems, which were previously the fastest, have a running time

$$n \cdot k \cdot (\log n)^{(O(\sqrt{d}/\epsilon))^{d-1}}$$

In this work, we give faster approximation schemes for both Euclidean k-TSP and Euclidean k-MST (Theorem 1). Comparing with [Aro98], the running time in Theorem 1 sheds the factor $k$ as well as the dependence in $\epsilon$ in the polylog $n$ factor.

**Theorem 1.** Let $d \ge 2$ be fixed. For any $\epsilon > 0$, there are randomized $(1 + \epsilon)$-approximation algorithms for the Euclidean k-TSP and the Euclidean k-MST that run in time

$$2^{O(1/\epsilon^{d-1})} \cdot n \cdot (\log n)^{d \cdot 4^d}.$$

Both algorithms can be derandomized by increasing the running time by a factor $O(n^d)$. Moreover, the running time of the algorithm for the Euclidean k-TSP is optimal under the Gap-Exponential Time Hypothesis (Gap-ETH).

To prove theorem 1, we focus on the algorithm for the Euclidean k-TSP. The algorithm for the Euclidean k-MST is analogous, as observed by Arora [Aro98].

First, in a preprocessing step, we partition the instance into subinstances that are easier to handle. The partition algorithm, which takes $O(n \cdot k \cdot \log n)$ time in [Aro98], is improved to $O(n)$ time (Theorem 7). This is achieved using a result on the enclosing circles due to Har-Peled and Raiche [HR15]. See Section 3.

Next, we solve each of those subinstances independently. This step, which is the most time-consuming part of the algorithm and takes $n \cdot k \cdot (\log n)^{(O(\sqrt{d}/\epsilon))^{d-1}}$ time in [Aro98], is improved to $2^{O(1/\epsilon^{d-1})} \cdot n \cdot (\log n)^{d \cdot 2^{2d}}$ time (Theorem 11). To that end, we combine the classical *quadtree decomposition* of Arora [Aro98] with the recent powerful technique of *sparsity-sensitive patching*, introduced by Kisfaludi-Bak, Nederlof, and Węgrzycki [KNW21]. This removes the dependence in $\epsilon$ in the polylog $n$ factor in the running time. To remove the factor $k$ in the running time, we introduce the *budget multipath problem* (Definition 14) using the notion of *budget thresholds* (Definition 13). This is inspired by Kolliopoulos and Rao [KR07] in the context of k-median. The combination of budget thresholds and the approach of Kisfaludi-Bak, Nederlof, and Węgrzycki [KNW21] is non-trivial and is the key to the claimed running time, see Section 4.

Finally, using the Gap-ETH lower bound for the Euclidean TSP due to Kisfaludi-Bak, Nederlof, and Węgrzycki [KNW21], we obtain the Gap-ETH tightness of our algorithm for the Euclidean k-TSP. See Section 5.

<footnote n="1">¹An approximation scheme is a $(1 + \epsilon)$-approximation algorithm for any $\epsilon > 0$.</footnote>
# 2 Preliminaries

In this section, we summarize techniques from Arora [Aro98] and Kisfaludi-Bak, Nederlof, and Węgrzycki [KNW21], which will be used in our algorithm. We follow the notations in [KNW21].

## 2.1 Dissection

Without loss of generality, we assume that the input points are in $\{0, \dots, L\}^d$ for some integer $L = O(n\sqrt{d}/\epsilon)$, see, e.g., [NS07, Section 19.2]. We pick a random shift $\mathbf{a} := (a_1, \dots, a_d) \in \{0, \dots, L\}^d$. Then we define the hypercube $C(\mathbf{a})$ as:

$$C(\mathbf{a}) := \times_{i=1}^{d} [-a_i + 1/2, 2L - a_i + 1/2].$$

We define the dissection $D(\mathbf{a})$ to be a tree $T$ defined recursively as follows. The root of $T$ is $C(\mathbf{a})$. Each non-leaf vertex of $T$ associated with the hypercube $\times_{i=1}^{d}[l_i, u_i]$ has $2^d$ children with which we associate $\times_{i=1}^{d} I_i$, where $I_i \in \{[l_i, (l_i + u_i)/2], [(l_i + u_i)/2, u_i]\}$. Each leaf vertex of $T$ is associated with a hypercube of side length one. Each hypercube associated with a vertex of the dissection is called a cell. The shifted quadtree is obtained from $D(\mathbf{a})$ by stopping the subdivision whenever a cell contains at most 1 input point. For each cell $C$, let $\partial C$ denote the boundary of $C$. The height of $C$ is defined to be the height of the subtree of $T$ rooted at $C$.

Let $F$ be a facet of a $d$-dimensional hypercube. We define $\text{grid}(F, m)$ as an orthogonal lattice of $m$ evenly placed points on $F$.

**Definition 2** (r-light, [Aro98]). A path is r-light with respect to a dissection if it crosses each of its faces at most r times.

A k-salesman path is a path visiting at least k points. Let $\text{opt}$ denote the optimal cost to the k-TSP.

**Theorem 3** (Arora's structure theorem, [Aro98]). We are given $\epsilon > 0$ and an instance of the Euclidean k-TSP. Let $\mathbf{a}$ be a random shift. With probability greater than $1/2$, there is a k-salesman path of cost at most $(1+\epsilon) \cdot \text{opt}$ that is r-light with respect to $D(\mathbf{a})$ and crosses each facet $F$ of cells of $D(\mathbf{a})$ only at points from $\text{grid}(F, m)$, with $m = (O((\sqrt{d}/\epsilon) \log L))^{d-1}$ and $r = (O(\sqrt{d}/\epsilon))^{d-1}$.

## 2.2 r-Simple Paths

To reduce the number of portals in Arora's approach, we use the sparsity-sensitive patching technique, which was introduced by Kisfaludi-Bak, Nederlof, and Węgrzycki [KNW21] to achieve r-simple paths.

**Definition 4** (r-simple paths, [KNW21]). A path (resp. set of paths) in $\mathbb{R}^d$ is r-simple if for every face $F$ of every cell in $D(\mathbf{a})$, either

* it crosses $F$ at only one point, or

* it crosses $F$ at most $m$ times, and only at points from $\text{grid}(F, g)$ for $g \le r^{2d-2}/m$.

Moreover, for any point $p$ on a hyperplane $h$, it can cross $h$ at most twice at $p$.

**Theorem 5** (adaptation from [KNW21]). Let $\mathbf{a}$ be a random shift. Let $\pi$ be a k-salesman path. For some $\tilde{m} = (O((\sqrt{d}/\epsilon) \log L))^{d-1}$ and any large enough $r$, there is a k-salesman path $\pi'$ which satisfies:
• $\mathbb{E}_a[wt(\pi') - wt(\pi)] \le O(d^2 \cdot wt(\pi)/r)$,

• $\pi'$ is r-simple, and

• if $\pi'$ crosses a facet F of a hypercube of $D(\mathbf{a})$ at only one point, this point belongs to $\text{grid}(F, \tilde{m})$.

*Proof.* The statement follows from Arora's structure theorem (Theorem 3) and Theorem III.3 in [KNW21]. □

<figure><img src="image_2.png" /></figure>

# 3 Partitioning Into Subinstances

**Definition 6** (well-rounded instance, [Aro98]). We say that an instance for Euclidean k-TSP is well-rounded if all points have integral coordinates, the minimum nonzero internode distance is at least 8, and the side length of the bounding box is $O(k^2)$.

**Theorem 7** (partition theorem). There is a randomized algorithm in expected $O(n)$ time that partitions the instance $\mathcal{I}$ into a family of well-rounded subinstances $\mathcal{I}_1, \dots, \mathcal{I}_\ell$ (where $\ell \ge 1$), such that with probability at least $1 - 2/\log k$, an optimal solution to $\mathcal{I}$ is completely within $\mathcal{I}_j$ for some $j \in [1, \ell]$. In addition, the algorithm can be derandomized by increasing the running time by a multiplicative factor $n$.

In the rest of the section, we prove Theorem 7.

As in [Aro98], the key in the partition algorithm is to compute a good approximation of the optimal cost. Fact 8 relates the optimal cost with the side length of the smallest hypercube containing $k$ points.

**Fact 8** ([Aro98]). The cost of the optimal solution to k-TSP is at most $dk^{1-(1/d)}$ times larger than the side length of the smallest hypercube containing $k$ points.

Estimating the smallest hypercube containing $k$ points takes $O(nk \log n)$ time in [Aro98]. We show that this can be improved to $O(n)$ time (Corollary 10), using the following result (Lemma 9) on the smallest ball due to Har-Peled and Raiche [HR15].

**Lemma 9** (Corollary 4.18 from [HR15]). For a set of $n$ points in $\mathbb{R}^d$ and a positive integer $k$, one can $(1 + \lambda)$-approximate, in expected $O(n/\lambda^d)$ time, the radius of the smallest ball containing $k$ points.

**Corollary 10.** For a set of $n$ points in $\mathbb{R}^d$ and a positive integer $k$, one can $2\sqrt{d}$-approximate, in expected $O(n)$ time, the side length of the smallest hypercube containing $k$ points.

*Proof.* Let $R^*$ denote the radius of the smallest ball containing $k$ points. Applying Lemma 9 with $\lambda = 1$, we obtain in expected $O(n)$ time an estimate $R$ such that $R^* \le R \le 2R^*$. On the one hand, there exists a hypercube of side length $2R^* \le 2R$ that contains at least $k$ points. On the other hand, since the longest diagonal of a hypercube is equal to $\sqrt{d}$ times the side length of that hypercube, any hypercube of side length $2R^*/\sqrt{d} \ge R/\sqrt{d}$ contains at most $k$ points. So the side length of the smallest hypercube containing $k$ points is in $[R/\sqrt{d}, 2R]$. The claim follows. □

*Proof of the partition theorem (Theorem 7).* From Fact 8 and Corollary 10, there is a randomized algorithm that computes in expected $O(n)$ time an estimate $A$ for the optimal cost of k-TSP such that

$$ \text{opt} \le A \le 2d^{3/2}k^{1-(1/d)} \cdot \text{opt}. $$
The first part of the claim follows from arguments that are almost identical to [Aro98], except by modifying the definition of the parameter $\rho$ to

$$ \rho := \frac{A\varepsilon}{16d^{3/2}k^{2-(1/d)}}. $$

Now we prove the second part of the claim. We only need to derandomize the algorithm in Corollary 10. This requires derandomizing the algorithm in Lemma 9, which is called **ndpAlg** in [HR15, Figure 3.1]. To that end, we remove Line 1 of the algorithm **ndpAlg** in [HR15], which randomly picks a point $p$ in $W_{i-1}$. Instead, we enumerate all points in $W_{i-1}$. For each point $p \in W_{i-1}$, we compute a set $W_i^p$ using Lines 2-7 of the algorithm **ndpAlg** in [HR15]. Finally, we let $W_i$ be the set $W_i^p$ with minimum cardinality for all points $p \in W_{i-1}$. This completes the description of the derandomized algorithm, see Algorithm 1.

<caption>**Algorithm 1:** Derandomized algorithm for **ndpAlg**</caption>

1. $W_0 \leftarrow W$
2. $i \leftarrow 1$
3. **while** true **do**
4. &nbsp;&nbsp;&nbsp;&nbsp;**forall** $p \in W_{i-1}$ **do**
5. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**L** Compute $W_i^p$
6. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;▷ Lines 2-7 of algorithm **ndpAlg** in [HR15]
7. &nbsp;&nbsp;&nbsp;&nbsp;**Let** $W_i$ be the set $W_i^p$ with minimum cardinality for all $p \in W_{i-1}$
&nbsp;&nbsp;&nbsp;&nbsp;**i** $\leftarrow i + 1$

It remains to analyze the running time of Algorithm 1. Let $\ell$ denote the number of iterations in the **while** loop in Algorithm 1. Consider any $i \in [1, \ell]$. From the proof of Lemma 3.12 in [HR15], for each $p \in W_{i-1}$, the set $W_i^p$ in Line 5 of Algorithm 1 can be computed in $O(|W_{i-1}|)$ time. So the overall time to compute $W_i^p$ over all $p \in W_{i-1}$ is $O(|W_{i-1}|^2)$. Using a similar analysis in the proof of Lemma 3.12 in [HR15], there exists some $p \in W_{i-1}$ such that $|W_i^p| \le (15/16)|W_{i-1}|$, thus $|W_i| \le (15/16)|W_{i-1}|$ by the definition of $W_i$. Therefore, the overall running time of Algorithm 1 is

$$ \sum_{i=1}^{\ell} O(|W_{i-1}|^2) \le \sum_{i=1}^{\ell} (15/16)^{i-1} \cdot O(|W_0|^2) = O(|W_0|^2) = O(n^2). $$

This completes the proof of the second part of the claim. □

# 4 Dynamic Programming

**Theorem 11** (dynamic programming theorem). Consider a well-rounded instance (Definition 6) with a set $P$ of $n$ points in $\mathbb{R}^d$ and a positive integer $k \le n$. There is a randomized $(1 + \varepsilon)$-approximation algorithm for the Euclidean $k$-TSP with running time $2^{O(1/\varepsilon^{d-1})} \cdot n \cdot (\log n)^{d \cdot 4^d}$. The algorithm can be derandomized, by increasing the running time by a factor $O(n^d)$.

In the rest of the section, we prove Theorem 11.

## 4.1 Budget Multipath Problem

**Definition 12** (fine set, adaptation from [KNW21]). Let $C$ be a cell in the shifted quadtree. Let $B$ be a set of points in the boundary of $C$. Let $\tilde{m} = (O((\sqrt{d}/\varepsilon) \log L))^{d-1}$ and $r = O(1/\varepsilon)$. We say that $B$ is fine if for all facets $F$ of $C$ either one of the two following conditions holds:
* $B \cap F = \{p\}$ and $p \in \text{grid}(F, \tilde{m})$, or

* $B \subseteq \text{grid}(F, r^{2d-2}/m_F)$ where $|B \cap F| \le m_F \le r^{d-1}$.

For each cell, we allow a *budget* on the solution cost within that cell. We discretize the budget to $(1 + \frac{\epsilon}{\log n})^i$ for some $i \in \mathbb{N}$. The result is called a *budget threshold* (Definition 13). This is the main difference from [KNW21] in the problem definition (Definition 14).

**Definition 13 (budget thresholds).** We say that $s \in [0, (1 + \epsilon)dk^{1-1/d}L]$ is a budget threshold, if there exists $i \in \mathbb{N}$ such that $(1 + \frac{\epsilon}{\log n})^i = s$. Let $S$ be the set of all budget thresholds.

It suffices to consider $s \in [0, (1 + \epsilon)dk^{1-1/d}L]$ since the cost of an optimal solution is at most $dk^{1-1/d}L$ and we are looking for a $1 + \epsilon$ approximation. Since $L = O(k^2) = O(n^2)$, there are at most $O(\log^2 n/\epsilon)$ different budget thresholds, i.e., $|S| = O(\log^2 n/\epsilon)$.

**Definition 14 (budget multipath problem).** In this problem, we are given:

* a cell $C$ in the shifted quadtree,

* a portal set $B \subseteq \partial C$ that is fine,

* a perfect matching $M$ on $B$,

* a budget threshold $s \in S$.

The goal is to find an $r$-simple path collection $\mathcal{P}_{B,M}$ maximizing the number of visited points that satisfies the following:

* $\mathcal{P}_{B,M}$ has total length at most $s$.

* $\mathcal{P}_{B,M}$ crosses $\partial C$ only through portals from $B$.

* $\mathcal{P}_{B,M}$ realizes the matching $M$ on $B$.

Computing the solutions of the budget multipath problem for all matchings would be too time-consuming. In order to be more efficient, we use a non-trivial adaptation of the rank-based approach from [KNW21], see also [BCKN15].

We follow the notations of [KNW21] and [BCKN15]. Given $M_1$ and $M_2$ two matchings, we denote $M_1 \sqcup M_2$ the result of the join of matchings defined in [BCKN15]. We say that two perfect matchings $M_1$ and $M_2$ on a set $B$ fit if their union is a Hamiltonian Cycle on $B$. Let $\mathcal{M}_B$ denote the set of all perfect matchings on $B$. For a set $A \subseteq \mathcal{M}_B \times \mathbb{N}$ and a fixed perfect matching $M \in \mathcal{M}_B$, define

$$ \text{opt}(M, A) := \max\{\kappa|(M', \kappa) \in A \text{ and } M \text{ fits } M'\} $$

**Definition 15 (representation, [KNW21]).** Let $B$ be a set. Let $A, B \subseteq \mathcal{M}_B \times \mathbb{N}$. We say that $A$ represents $B$ if for all $M \in \mathcal{M}_B$ we have $\text{opt}(M, A) = \text{opt}(M, B)$.

The following result from [BCKN15] is a crucial part of the rank-based approach.

**Lemma 16 (reduce, [BCKN15]).** There exists an algorithm reduce that given a set $B$ and $A \subseteq \mathcal{M}_B \times \mathbb{N}$, outputs in time $|A| \cdot 2^{O(|B|)}$ a set $A' \subseteq A$ such that $A'$ represents $A$ and $|A'| \le 2^{|B|-1}$.
## 4.2 Algorithm

We compute for each cell $C$ and each budget threshold $s \in S$ a family $\{\mathcal{R}_s^C[B]\}_{B \subseteq \partial C}$ fine where each $\mathcal{R}_s^C[B]$ is a set of pairs, each pair consisting of a matching $M$ on $B$ and an integer $\kappa$. Intuitively, $\kappa$ is an approximation of the maximum number of points that can be visited in order to achieve the connectivity configuration corresponding to the matching $M$, and with total cost at most $s$.

We denote

$$ \mathcal{R}_s^C := \bigcup_{B \subseteq \partial C \text{ fine}} \mathcal{R}_s^C[B] $$

### 4.2.1 Leaf Cells

Let $C$ be a leaf cell. Thus $C$ contains at most one input point. Consider a fine set $B \subseteq \partial C$. We compute $\mathcal{R}_s^C[B]$ in non-decreasing order of $|B|$.

**Case 1:** $|B| = 0$. $\mathcal{R}_s^C[B] := \{(\emptyset, 0)\}$.

**Case 2:** $|B| = 2$. Let $u, v$ be the two elements in $B$. When $|C \cap P| = 0$, we have

$$ \mathcal{R}_s^C[\{u, v\}] := \begin{cases} \{(\{(u, v)\}, 0)\} & \text{if } \mathrm{dist}(u, v) \le s \\ \emptyset & \text{if } \mathrm{dist}(u, v) > s \end{cases} $$

When $|C \cap P| = 1$, letting $p$ denote the point in $C \cap P$, we have

$$ \mathcal{R}_s^C[\{u, v\}] := \begin{cases} \{(\{(u, v)\}, 1)\} & \text{if } \mathrm{dist}(u, p) + \mathrm{dist}(p, v) \le s \\ \{(\{(u, v)\}, 0)\} & \text{if } \mathrm{dist}(u, v) \le s < \mathrm{dist}(u, p) + \mathrm{dist}(p, v) \\ \emptyset & \text{if } \mathrm{dist}(u, v) > s \end{cases} $$

**Case 3:** $|B| > 2$. We use the following induction formula:

$$ \mathcal{R}_s^C[B] := \text{reduce} \left( \bigcup_{s_1+s_2 \le s} \bigcup_{\substack{u,v \in B \\ s_1, s_2 \in S}} \left\{ (M \sqcup \{(u,v)\}, \kappa) \middle| (M, \kappa) \in \mathcal{R}_{s_1}^C[B \setminus \{u,v\}], \mathrm{dist}(u,v) \le s_2 \right\} \right) $$

### 4.2.2 Non-Leaf Cells

Let $C$ be a non-leaf cell, $s$ a budget threshold and $B \subseteq \partial C$ a portal set that is fine. We combine the solution of cells of its children. Let $C_1, \dots, C_{2d}$ be the children of $C$ in the quadtree. Then, we iterate over all ways to split the budget threshold among the children, $s_1, \dots, s_{2d} \in S$ such that $\sum_i s_i \le s$. For all matchings $(M_1, \kappa_1) \in \mathcal{R}_{s_1}^{C_1}, \dots, (M_{2d}, \kappa_{2d}) \in \mathcal{R}_{s_{2d}}^{C_{2d}}$ that are compatible, meaning that the endpoints of matchings on a shared facet are the same and combining them results in a set of paths with endpoints in $\partial C$, we join them into a matching $M$. If the set of endpoints of $M$ is $B$, we insert $(M, \sum_i \kappa_i)$ into $\mathcal{R}_s^C(B)$. Once we iterated through all possibilities, we apply **reduce** to $\mathcal{R}_s^C[B]$.
<caption>**Algorithm 2: BudgetMultipath(C, s, B)**</caption>

1 if C is a leaf cell then
2     if $|B| = 0$ then
3         $\mathcal{R}_s^C[B] \leftarrow \{(\emptyset, 0)\}$
4     else if $|B| = 2$ then
5         Let $u$ and $v$ be the two portals in B
6             if $|C \cap P| = 1$ then
7                 Let $p$ be the point in $C \cap P$
8                 if $\text{dist}(u, p) + \text{dist}(p, v) \le s$ then
9                     $\mathcal{R}_s^C[B] \leftarrow \{(\{(u, v)\}, 1)\}$
10                 else if $\text{dist}(u, v) \le s$ then
11                     $\mathcal{R}_s^C[B] \leftarrow \{(\{(u, v)\}, 0)\}$
12             else
13                 $\mathcal{R}_s^C[B] \leftarrow \emptyset$
14     else
15         if $\text{dist}(u, v) \le s$ then
16             $\mathcal{R}_s^C[B] \leftarrow \{(\{(u, v)\}, 0)\}$
17     else
18         $\mathcal{R}_s^C[B] \leftarrow \emptyset$
19 else
20     for $s_1, s_2 \in S$ such that $s_1 + s_2 \le s$ do
21         for $u, v \in B$ such that $u \ne v$ do
22             for $(M, \kappa) \in \mathcal{R}_{s_1}^C[B \setminus \{u, v\}]$ do
23                 if $\text{dist}(u, v) \le s_2$ then
24                     Insert $(M \cup \{(u, v)\}, \kappa)$ into $\mathcal{R}_s^C[B]$
25         $\mathcal{R}_s^C[B] \leftarrow \text{reduce}(\mathcal{R}_s^C[B])$
26 else
27     Let $C_1, \dots, C_{2d}$ be the children of C
28     for $s_1, \dots, s_{2d} \in S$ such that $\sum_i s_i \le s$ do
29         for $(M_1, \kappa_1) \in \mathcal{R}_{s_1}^C, \dots, (M_{2d}, \kappa_{2d}) \in \mathcal{R}_{s_{2d}}^{C_{2d}}$ do
30             if $M_1, \dots, M_{2d}$ are compatible then
31                 Let $M \leftarrow M_1 \cup \dots \cup M_{2d}$
32                 if the set of endpoints of M equals B then
33                     Insert $(M, \sum_i \kappa_i)$ into $\mathcal{R}_s^C[B]$
34         $\mathcal{R}_s^C[B] \leftarrow \text{reduce}(\mathcal{R}_s^C[B])$
$$
\mathcal{R}_s^C[B] := \text{reduce} \left( \bigcup_{\substack{s_1, \dots, s_{2d} \in S \\ s_1 + \dots + s_{2d} \le s}} \bigcup_{\substack{(M_1, \kappa_1) \in \mathcal{R}_{s_1}^{C_1}, \dots, (M_{2d}, \kappa_{2d}) \in \mathcal{R}_{s_{2d}}^{C_{2d}} \\ \text{s.t. the set of endpoints of } \bigcup_i M_i \text{ equals } B}} \{(\bigcup_i M_i, \sum_i \kappa_i)\} \right)
$$

We compute $\mathcal{R}_s^C(B)$ in the bottom up order of the cell $C$ in the decomposition, and for the same cell $C$, in increasing order of the threshold $s \in S$, and for a given $s$, in non-decreasing order of $|B|$. For each cell $C$, budget threshold $s$ and portal set $B$ that is fine, we compute the value of $\mathcal{R}_s^C[B]$ using Algorithm 2.

4.3 Analysis

Let $C$ be a cell in the shifted quadtree and $s \in S$ be a budget threshold. We define the family $\{\mathcal{M}_s^C(B)\}_B$ as follows.

* If $C$ is a leaf in the quadtree, we define $\mathcal{M}_s^C(\emptyset) = \{(\emptyset, 0)\}$, for all fine portal sets $B = \{u, v\} \subseteq \partial C$ of size 2, when $|C \cap P| = 0$, we let

$$
\mathcal{M}_s^C(\{u, v\}) := \begin{cases} \{(\{(u, v)\}, 0)\} & \text{if } \mathrm{dist}(u, v) \le s \\ \emptyset & \text{if } \mathrm{dist}(u, v) > s \end{cases}
$$

and when $|C \cap P| = 1$, letting $p$ denote the point in $C \cap P$, we let

$$
\mathcal{M}_s^C(\{u, v\}) := \begin{cases} \{(\{(u, v)\}, 1)\} & \text{if } \mathrm{dist}(u, p) + \mathrm{dist}(p, v) \le s \\ \{(\{(u, v)\}, 0)\} & \text{if } \mathrm{dist}(u, v) \le s < \mathrm{dist}(u, p) + \mathrm{dist}(p, v) \\ \emptyset & \text{if } \mathrm{dist}(u, v) > s \end{cases}
$$

and for $|B| > 2$,

$$
\mathcal{M}_s^C(B) := \bigcup_{\substack{s_1+s_2 \le s \\ s_1, s_2 \in S}} \bigcup_{\substack{u,v \in B \\ u \ne v}} \{(M \cup \{(u,v)\}, \kappa) | (M, \kappa) \in \mathcal{M}_{s_1}^C(B \setminus \{u,v\}), \mathrm{dist}(u,v) \le s_2\}
$$

* If $C$ is a non-leaf cell, let $C_1, \dots, C_{2d}$ be the children of $C$. We let

$$
\mathcal{M}_s^C(B) := \bigcup_{\substack{s_1, \dots, s_{2d} \in S \\ s_1 + \dots + s_{2d} \le s}} \bigcup_{\substack{(M_1, \kappa_1) \in \mathcal{M}_{s_1}^{C_1}, \dots, (M_{2d}, \kappa_{2d}) \in \mathcal{M}_{s_{2d}}^{C_{2d}} \\ \text{s.t. the set of endpoints of } \bigcup_i M_i \text{ equals } B}} \{(\bigcup_i M_i, \sum_i \kappa_i)\}
$$

**Lemma 17.** For a cell *C*, a budget threshold *s* and a fixed *B* that is fine, the set $\mathcal{R}_s^C[B]$ computed in algorithm *BudgetMultipath*(*C*, *s*, *B*) represents $\mathcal{M}_s^C(B)$.

*Proof.* The proof combines Lemma 3.6 of [BCKN15] with an induction. We prove by induction in the bottom up order on the cell *C*.
When the cell is a leaf, we proceed by induction on the size of $B$. If $|B| \le 2$, it is clear that $\mathcal{R}_s^C[B]$ represents $\mathcal{M}_s^C(B)$. For $|B| > 2$:

$$
\begin{align*}
\operatorname{opt}(M, \mathcal{R}_s^C[B]) &= \max\{\kappa|u, v \in B, u \neq v, s_1 + s_2 \le s, (M', \kappa) \in \mathcal{R}_{s_1}^C[B \setminus \{u, v\}], \\
&\quad \operatorname{dist}(u, v) \le s_2, M \text{ fits } \{(u, v)\} \sqcup M'\} \\
&= \max\{\operatorname{opt}(M \sqcup \{(u, v)\}, \mathcal{R}_{s_1}^C[B \setminus \{u, v\}]), u, v \in B, u \neq v, \operatorname{dist}(u, v) \le s_2, s_1 + s_2 \le s\} \\
&= \max\{\operatorname{opt}(M \sqcup \{(u, v)\}, \mathcal{M}_{s_1}^C[B \setminus \{u, v\}]), u, v \in B, u \neq v, \operatorname{dist}(u, v) \le s_2, s_1 + s_2 \le s\} \\
&= \max\{\kappa|u, v \in B, u \neq v, s_1 + s_2 \le s, (M', \kappa) \in \mathcal{M}_{s_1}^C(B \setminus \{u, v\}), \\
&\quad \operatorname{dist}(u, v) \le s_2, M \text{ fits } \{(u, v)\} \sqcup M'\} \\
&= \operatorname{opt}(M, \mathcal{M}_s^C(B))
\end{align*}
$$

therefore $\mathcal{R}_s^C[B]$ represents $\mathcal{M}_s^C(B)$.

For non-leaf cells, we have:

$$
\begin{align*}
\operatorname{opt}(M, \mathcal{R}_s^C[B]) &= \max\{\kappa|(M', \kappa) \in \mathcal{R}_s^C[B], M \text{ fits } M'\} \\
&= \max\{\sum_i \kappa_i|(M_i, \kappa_i) \in \mathcal{R}_{s_i}^{C_i}, (C_i)_i \text{ children of } C, \sum_i s_i \le s, \bigsqcup_i M_i \text{ fits } M\} \\
&= \max\{\operatorname{opt}(\bigsqcup_{i>1} M_i \sqcup M, \mathcal{R}_{s_1}^{C_1}) + \sum_{i>1} \kappa_i | \forall i > 1, (M_i, \kappa_i) \in \mathcal{R}_{s_i}^{C_i}, \sum_i s_i \le s\} \\
&= \max\{\operatorname{opt}(\bigsqcup_{i>1} M_i \sqcup M, \mathcal{M}_{s_1}^{C_1}) + \sum_{i>1} \kappa_i | \forall i > 1, (M_i, \kappa_i) \in \mathcal{R}_{s_i}^{C_i}, \sum_i s_i \le s\} \\
&= \max\{\sum_i \kappa_i|(M_1, s_1) \in \mathcal{M}_{s_1}^{C_1}, \forall i > 1, (M_i, \kappa_i) \in \mathcal{R}_{s_i}^{C_i}, \sum_i s_i \le s, \bigsqcup_i M_i \text{ fits } M\} \\
&= \max\{\sum_i \kappa_i|(M_i, \kappa_i) \in \mathcal{M}_{s_i}^{C_i}, \sum_i s_i \le s, \bigsqcup_i M_i \text{ fits } M\} \\
&= \max\{\kappa|(M', \kappa) \in \mathcal{M}_s^C(B), M \text{ fits } M'\} \\
&= \operatorname{opt}(M, \mathcal{M}_s^C(B))
\end{align*}
$$

Hence by induction, $\mathcal{R}_s^C[B]$ represents $\mathcal{M}_s^C(B)$. $\square$

<figure><img src="image_3.png" /></figure>

Let $\mathcal{R}$ be the maximum size of any $\mathcal{R}_s^C$. Let $\mathcal{B}$ be the maximum size of any portal set that is fine in any cell. Let $\mathcal{F}$ be the maximum over all cells of the number of choices for a portal set that is fine.

**Lemma 18.** *Computing BudgetMultipath for all (C, s, B) using Algorithm 2 takes time $O(\mathcal{F} \cdot \mathcal{B}^2 \cdot n \log^{2d+1} n \cdot \mathcal{R}^{2d} \cdot (1/\varepsilon)^{2d})$.*

*Proof.* There are $O(n \log n)$ cells in the quadtree, $|\mathcal{S}|$ possible budget thresholds and at most $\mathcal{F}$ choices for the portal set. When $C$ is a leaf, Algorithm 2 runs in time $O(|\mathcal{S}|^2 \cdot \mathcal{B}^2 \cdot \mathcal{R}) = O(\mathcal{B}^2 \cdot \log^4 n \cdot (1/\varepsilon)^2 \cdot \mathcal{R})$. When $C$ isn't a leaf, it runs in time $O(|\mathcal{S}|^{2d} \cdot \mathcal{R}^{2d}) = O(\log^{2 \cdot 2d} n \cdot (1/\varepsilon)^{2d} \cdot \mathcal{R}^{2d})$. Therefore, computing Algorithm 2 for all $(C, s, B)$ runs in time $O(\mathcal{F} \cdot \mathcal{B}^2 \cdot n \log^{2d+1} n \cdot \mathcal{R}^{2d} \cdot (1/\varepsilon)^{2d})$. $\square$

We now bound $\mathcal{F} \cdot \mathcal{B}^2 \cdot \mathcal{R}^{2d} \cdot (1/\varepsilon)^{2d}$.

**Fact 19.** $\mathcal{F} \cdot \mathcal{B}^2 \cdot \mathcal{R}^{2d} \cdot (1/\varepsilon)^{2d} = 2^{O(r^{d-1})} \cdot \log^{(d-1)(2d+4d)} n$.
Proof. The proof is similar to Claim 5.5 in [KNW21]. From [KNW21], we have

$$ \mathcal{B} \le 2^d r^{d-1}. $$

Next, we bound $\mathcal{F}$. Let $C$ be a cell and $F$ be one of its facets. We select a set $B \cap F$ of size $b_F$, where the points can be chosen from $\text{grid}(F, r^{2d-2}/m_F)$ where $|B \cap F| \le m_F \le r^{d-1}$ or, when there is exactly one crossing on one of the $2^d$ facets, it is chosen from $\text{grid}(F, \tilde{m})$. Hence

$$ \mathcal{F} \le \tilde{m}^{2^d} \cdot \prod_F \left( \sum_{m_F=1}^{(2r)^{d-1}} \sum_{b_F=1}^{m_F} \binom{r^{2d-2}/m_F}{b_F} \right). $$

Arora's structure theorem (5) ensures that $\tilde{m} \le O((\sqrt{d}/\epsilon) \log L)^{d-1}$. By [KNW21], $(\binom{r^{2d-2}/m_F}{b_F})$ is at most $2^{O(r^{d-1})}$. Therefore,

$$ \mathcal{F} = O(((\sqrt{d}/\epsilon) \log L)^{(d-1)2^d}) \cdot \prod_F \left( \sum_{m_F=1}^{(2r)^{d-1}} \sum_{b_F=1}^{m_F} 2^{O(r^{d-1})} \right) = 2^{O(r^{d-1})} \cdot \log^{(d-1)2^d} n. $$

Since we apply reduce to each $\mathcal{R}_s^C[B]$, each resulting $\mathcal{R}_s^C[B]$ has size at most $2^{\beta-1}$ by Lemma 16. Thus $\mathcal{R} \le \mathcal{F} \cdot 2^{\beta-1}$. Therefore,

$$ \mathcal{R}^{2^d} = (2^{O(r^{d-1})} \cdot \log^{(d-1)2^d} n)^{2^d} \cdot 2^{2^d \cdot (2^d r^{d-1} - 1)} = 2^{O(r^{d-1})} \cdot \log^{(d-1)4^d} n. $$

Multiplying the above factors completes the proof. $\square$

<figure><img src="image_4.png" /></figure>

Finally, we show that the discretization of the budget thresholds inspired by [KR07] provides a good approximation ratio.

**Lemma 20.** Let OPT be an $r$-simple solution. Let $C$ be any cell. Let $\text{opt}_C$ denote the cost of the optimal solution OPT inside $C$. Let $k_C$ denote the number of points in $C$ that belong to OPT. Let $h_C$ denote the height of the cell $C$. Let $B$ denote the set of portals on the boundary of $C$ that belong to OPT. Let $M$ denote the matching in $\text{OPT} \cap C$ among the points in $B$. Then we have $(M, k'_C) \in \mathcal{M}_s^C(B)$ where $s \in S$ is such that $s \le \text{opt}_C \cdot (1 + \epsilon/\log n)^{2r+h_C}$ and $k'_C \ge k_C$.

*Proof.* First, consider the case when $C$ is a leaf cell. Since OPT is $r$-simple, OPT crosses the boundary of $C$ at most $4r$ times. Thus $|B| \le 4r$. Since the cost inside $C$ is obtained after at most $|B|/2 \le 2r$ rounding operations, there exists $s \in S$ such that $s \le \text{opt}_C \cdot (1 + \epsilon/\log n)^{2r}$ such that $(M, k_c) \in \mathcal{M}_s^C(B)$ for some $k'_c \ge k_c$. The claim follows.

Next, consider the case when $C$ is a non-leaf cell. Let $C_1, \dots, C_{2d}$ be the children of $C$ in the decomposition. By induction, for each $i \in [1, 2^d]$, We have $(M_i, k'_{C_i}) \in \mathcal{M}_{s_i}^{C_i}(B_i)$ where $s_i \in S$ is such that $s_i \le \text{opt}_{C_i} \cdot (1 + \epsilon/\log n)^{2r+h_{C_i}}$ and $k'_{C_i} \ge k_{C_i}$. We have

$$ k'_C \ge \sum_i k'_{C_i} \ge \sum_i k_{C_i} = k_C. $$

Combining the solutions in all $C_i$ and noting that $h_C \ge h_{C_i} + 1$ for all $i$, we have

$$ \begin{align*} s &\le (1 + \epsilon/\log n) \cdot \sum_i s_i \\ &\le (1 + \epsilon/\log n) \cdot \sum_i \text{opt}_{C_i} \cdot (1 + \epsilon/\log n)^{2r+h_{C_i}} \\ &\le (1 + \epsilon/\log n)^{2r+h_C} \sum_i \text{opt}_{C_i} \\ &= (1 + \epsilon/\log n)^{2r+h_C} \cdot \text{opt}_C. \end{align*} $$

This completes the proof of the claim. $\square$

<figure><img src="image_5.png" /></figure>
We are now able to prove Theorem 11.

*Proof.* Once we have applied algorithm BudgetMultipath to the root of the quadtree for all budget thresholds, we are done. Indeed, we just need to find the smallest budget threshold $s$ such that there is a matching of cardinal at least $k$ on the empty set (because the tour has to be continuous) in the $R_s$ corresponding to the root. This is guaranteed to happen for some budget threshold because of lemma 17. The approximation ratio follows from lemma 20. The running time follows from the combination of lemma 18 and fact 19:

$$F \cdot B^2 \cdot n \log^{2d+1} n \cdot R^{2d} \cdot (1/\varepsilon)^{2d} = 2^{O(r^{d-1})} \cdot \log^{(d-1)(2d+4d)} n \cdot n \log^{2d+1} n \le 2^{O(r^{d-1})} \cdot n \cdot \log^{d \cdot 4d} n.$$

The only step using randomness is the random shift to construct the quadtree. Since there are $O(n^d)$ possible shifts, the whole algorithm can be derandomized by increasing the running time by a factor $O(n^d)$. □

# 5 Gap-ETH Tightness

**Gap Exponential Time Hypothesis (Gap-ETH) ([MR17], [Din16]).** There exist constants $\delta, \gamma > 0$ such that there is no $2^{\gamma m}$ algorithm which, given a 3-CNF formula $\phi$ on $m$ clauses, can distinguish between the cases where (i) $\phi$ is satisfiable or (ii) all variable assignments violate at least $\delta m$ clauses.

**Theorem 21 ([KNW21]).** For any $d$ there is a $\gamma > 0$ such that there is no $2^{\gamma/\varepsilon^{d-1}}$ poly($n$) time $(1+\varepsilon)$-approximation algorithm for Euclidean TSP in $\mathbb{R}^d$, unless Gap-ETH fails.

Since Euclidean TSP on $n$ points is a special case of Euclidean $k$-TSP with $k=n$, we derive the following corollary:

**Corollary 22.** For any $d$ there is a $\gamma > 0$ such that there is no $2^{\gamma/\varepsilon^{d-1}}$ poly($n$) time $(1+\varepsilon)$-approximation algorithm for Euclidean $k$-TSP in $\mathbb{R}^d$, unless Gap-ETH fails.

# Acknowledgements

We thank Tobias Mömke, Noé Weeks, and Antoine Stark for discussions.

# References

[Aro98] Sanjeev Arora. Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. *Journal of the ACM (JACM)*, 45(5):753–782, 1998.

[BCKN15] Hans L. Bodlaender, Marek Cygan, Stefan Kratsch, and Jesper Nederlof. Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth. *Information and Computation*, 243:86–111, 2015.

[BCV95] Avrim Blum, Prasad Chalasani, and Santosh Vempala. A constant-factor approximation for the $k$-MST problem in the plane. In *Proceedings of the twenty-seventh annual ACM Symposium on Theory of Computing (STOC)*, pages 294–302, 1995.

[Din16] Irit Dinur. Mildly exponential reduction from gap-3SAT to polynomial-gap label-cover. In *Electronic colloquium on computational complexity (ECCC)*, 2016.
[Epp97] David Eppstein. Faster geometric $k$-point MST approximation. *Computational Geometry*, 8(5):231–240, 1997.

[FHJM94] Matteo Fischetti, Horst W. Hamacher, Kurt Jørnsten, and Francesco Maffioli. Weighted $k$-cardinality trees: Complexity and polyhedral structure. *Networks*, 24(1):11–21, 1994.

[GGJ76] Michael R. Garey, Ronald L. Graham, and David S. Johnson. Some NP-complete geometric problems. In *Proceedings of the eighth annual ACM Symposium on Theory of Computing (STOC)*, pages 10–22, 1976.

[GH94] Naveen Garg and Dorit S. Hochbaum. An $O(\log k)$ approximation algorithm for the $k$-minimum spanning tree problem in the plane. In *Proceedings of the twenty-sixth annual ACM Symposium on Theory of Computing (STOC)*, pages 432–438, 1994.

[HR15] Sariel Har-Peled and Benjamin Raichel. Net and prune: A linear time algorithm for Euclidean distance problems. *Journal of the ACM (JACM)*, 62(6):1–35, 2015.

[KNW21] Sándor Kisfaludi-Bak, Jesper Nederlof, and Karol Węgrzycki. A Gap-ETH-tight approximation scheme for Euclidean TSP. In *IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS)*, pages 351–362. IEEE, 2021.

[KR07] Stavros G. Kolliopoulos and Satish Rao. A nearly linear-time approximation scheme for the Euclidean $k$-median problem. *SIAM Journal on Computing*, 37(3):757–782, 2007.

[MBCV98] Joseph S. B. Mitchell, Avrim Blum, Prasad Chalasani, and Santosh Vempala. A constant-factor approximation algorithm for the geometric $k$-MST problem in the plane. *SIAM Journal on Computing*, 28(3):771–781, 1998.

[Mit99] Joseph S. B. Mitchell. Guillotine subdivisions approximate polygonal subdivisions: A simple polynomial-time approximation scheme for geometric tsp, $k$-MST, and related problems. *SIAM Journal on Computing*, 28(4):1298–1309, 1999.

[MM95] Cristian S. Mata and Joseph S. B. Mitchell. Approximation algorithms for geometric tour and network design problems. In *Proceedings of the eleventh annual Symposium on Computational Geometry (SoCG)*, pages 360–369, 1995.

[MR17] Pasin Manurangsi and Prasad Raghavendra. A birthday repetition theorem and complexity of approximating dense CSPs. *44th Internation Colloquium on Automata, Languages, and Programming (ICALP 2017)*, 2017.

[NS07] Giri Narasimhan and Michiel Smid. *Geometric spanner networks*. Cambridge University Press, 2007.

[RSM+96] Ramamurthy Ravi, Ravi Sundaram, Madhav V. Marathe, Daniel J. Rosenkrantz, and Sekharipuram S. Ravi. Spanning trees—short or small. *SIAM Journal on Discrete Mathematics*, 9(2):178–200, 1996.