Maximum Scatter TSP in Doubling Metrics
László Kozma∗

Tobias Mömke∗ ‡scatter. We study this problem in the geometric setting where the metric d(·) has specific properties, for
We study the problem of finding a tour of n points
instance, when it is the Euclidean distance between
in which every edge is long. More precisely, we wish
points.
to find a tour that visits every point exactly once,
Arkin, Chiang, Mitchell, Skiena, and Yang [2, 3]
maximizing the length of the shortest edge in theinitiated the study of MSTSP in 1997, motivated by
tour. The problem is known as Maximum Scatterproblems in manufacturing (riveting) and medical
TSP, and was introduced by Arkin et al. (SODA
imaging. Similarly to other variants of TSP, solving1997), motivated by applications in manufacturing
MSTSP exactly is NP-hard. Therefore, the best weand medical imaging. Arkin et al. gave a 0.5can hope for are approximations, i. e., algorithms
approximation for the metric version of the problem
that compute a tour whose scatter is at least aand showed that this is the best possible ratio
factor c of the optimum, where 0 < c < 1. We
achievable in polynomial time (assuming P 6= NP).
call such an algorithm (as well as its output) a
Arkin et al. raised the question of whether a betterc-approximation. We are mostly concerned withapproximation ratio can be obtained in the Euclidean
algorithms that compute a solution that is at least aplane.
factor 1 − ε of the optimum, for an arbitrary constant
We answer this question in the affirmative in a
ε > 0. Such an algorithm is called a polynomial-time
more general setting, by giving a (1−ε)-approximation
approximation scheme (PTAS), if its running time isalgorithm for d-dimensional doubling metrics, withpolynomial in n for every fixed value of ε. An efficientdrunning time Õ n3 + 2O(K log K) , where K ≤ 13
. polynomial-time approximation scheme (EPTAS) is aεAs a corollary we obtain (i) an efficient polynomial- PTAS that has running time f (ε)·nk for some constanttime approximation scheme (EPTAS) for all constant k (not depending on ε), and an arbitrary function f .
dimensions d, (ii) a polynomial-time approximation
For the metric MSTSP (i. e., the case in whichscheme (PTAS) for dimension d = log log n/c, for the distance function d(·) is a metric, with no furthera sufficiently large constant c, and (iii) a PTAS for restrictions), Arkin et al. give a 0.5-approximation.
constant d and ε = Ω(1/ log log n). Furthermore, They also show that for this variant of the problem,
we show the dependence on d in our approximation the ratio of 0.5 is the best possible in polynomial
scheme to be essentially optimal, unless Satisfiability time (assuming P 6= NP). They leave open thecan be solved in subexponential time.
question of whether a better approximation ratio canbe obtained if the problem has geometric structure
1 Introduction(e. g., if the distances are Euclidean). Arkin et al.
Let P = {p1 , . . . , pn } be a set of points in some raise this question for the two-dimensional case (seemetric space with distance function d(·). A tour also [15, §49, p. 65] and [33, p. 681]).
T of P is a sequence T = (pi1 , . . . , pin ), where{i1 , . . . , in } = {1, . . . , n}. The scatter of T is the MSTSP and other TSP variants. TSP is one
minimum distance between neighboring points, i. e., of the cornerstones of combinatorial optimizationand several variants have been considered in the
min d(pi1 , pi2 ), . . . , d(pin−1 , pin ), d(pin , pi1 ) .
literature (we refer to [21, 27] for surveys). Minimizing
variants are more common, but there exist natural
The Maximum Scatter Traveling Salesman Prob- settings in which tours with long edges are desirable.
lem (MSTSP) asks for a tour of P with maximum This is the case in certain manufacturing operations
where nearby elements in a sequence are required
to be geometrically well-separated in order to avoid∗ Saarland University,
Saarland Informatics Campus.
interferences [2]. Informally, the difficulty of TSP
kozma@cs.uni-saarland.de, moemke@cs.uni-saarland.de‡ Funded by Deutsche Forschungsgemeinschaft grantvariants with maximized objective functions lies in theBL511/10-1 and MO 2889/1-1.
fact that the solutions are highly non-local, making
Abstractit hard to decompose the problem using standard
techniques. (This is true both for algorithms and for
hardness-proofs.)
In a certain sense, it is natural to expectthat geometric structure should lead to stronger
approximation-guarantees for MSTSP. The same phenomenon has been observed in case of the standard
TSP. For metric TSP the best known approximation
ratio is 1.5 (Christofides [12]), with a current lower
bound of 123
122 (Karpinski et al. [24]), whereas for Euclidean TSP, Arora [4] and Mitchell [28] independently
found a PTAS. Similarly, Euclidean MaxTSP (where
the goal is to maximize the total length of the tour)
admits a PTAS (Barvinok [8]), but the metric version
is known to be MaxSNP-hard [31, 8], ruling out theexistence of a PTAS (assuming P 6= NP). On thepositive side, metric MaxTSP is currently known toadmit a 78 -approximation (Kowalik and Mucha [25]).
The situation, however, is very different in thecase of Bottleneck TSP (a.k.a. min max TSP), whichis the TSP variant perhaps most similar to MSTSP(a.k.a. max min TSP). For metric Bottleneck TSP, a2-approximation can be achieved in polynomial time,
and this ratio is the best possible, assuming P 6= NP(Doroshko and Sarvanov [16], and independently
Parker and Rardin [32]). Surprisingly, for Bottleneck
TSP, geometric structure does not help. As shownby Sarvanov1 [34] in 1995, the factor of 2 can not be
improved even in the two-dimensional Euclidean case.
Based on these results for related problems, it is apriori not clear whether Euclidean MSTSP should
admit good approximations.

Our approximation scheme carries over to themore general case of doubling metrics. The doubling
dimension of a metric space D with metric d(·) is thesmallest k such that every ball of radius r in D can becovered by 2k balls of radius r/2. If k is finite, we also
refer to D and d(·) as a doubling space, resp. doubling
metric. Metric spaces with doubling dimension O(d)generalize the Euclidean space with d dimensions, andare significantly more general (see e. g., [20, 7, 13, 35]
and references therein).
Arguments for Euclidean spaces do not always
extend to doubling spaces. For instance, in the caseof the standard TSP, the question of whether a PTAS
exists in doubling spaces has been open for many
years [35], and was settled only recently [7, 6].
Our main result is the following.
Theorem 1.1. (EPTAS) Let P be a set of n points
in a metric space with doubling dimension d. A tourof P whose scatter is at least a (1 − ε) factor of the
MSTSP optimum can be found in time O(n3 log n +d2O(K log K) log n + K 3 log2 n), where K ≤ 13.
ε

We show that the running time in Theorem 1.1
is close to optimal (apart from the involved constants
and lower order factors). A result of Trevisan [36]shows that for Ω(log n)-dimensional Euclidean spaces,
TSP is APX-hard, and thus admits no PTAS, unless
P = NP. Adapting the proof technique of Trevisan to
MSTSP, we show that an approximation scheme for
MSTSP with an improved dependence on d would
give a subexponential-time algorithm for TSP in
bipartite cubic graphs, contradicting the exponentialtime hypothesis (ETH). More precisely, we show the
Results and techniques. We answer the open quesfollowing.
tion about Euclidean MSTSP, by giving an efficientpolynomial-time approximation scheme (EPTAS) for Theorem 1.2. For each p ≥ 1, there is a constantarbitrary fixed-dimensional Euclidean spaces. Since c such that a (3/4)1/p -approximation algorithm with
MSTSP is known to be strongly NP-hard in dimen- running time 22o(d) for MSTSP in Rd for d ≥ c log nsions 3 and above [17, 9], our result settles the classical and distances according to the `p norm contradicts thecomplexity status of the problem in these dimensions. ETH.
If the dimension d is superconstant (i. e., dependThe main ingredient of the algorithm in Theoing on n), we still obtain a PTAS if the dependence
on n is mild, i. e., d = log log n/c for a sufficiently rem 1.1 is a rounding scheme, whereby we replace thelarge constant c. Alternatively, for constant d we may original point set with points of a grid (or an ε-net).
choose ε to be asymptotically smaller than 1 depend- As subproblems, we solve perfect matching and Euleing on n, e. g., as ε = Θ(1/ log log n), and still obtain rian tour instances, and we use the many-visits TSP
algorithm of Cosmadakis and Papadimitriou [14].
a PTAS.
In order to introduce some of the ideas and tools
used for proving the result, we first describe a PTAS
that is simpler than our main algorithm but has
1 The result of Sarvanov is available as a technical report in
weaker guarantees. This result already settles theRussian, and appears to be not widely known in the Englishopen question about MSTSP by using only elementary
language literature (the only reference we are aware of is [26]and various sources incorrectly mention the problem as still techniques. However, due to its prohibitive runningopen). We thank Victor Lepin for providing us with a copy of time, it is only of theoretical (and perhaps didactic)
Sarvanov’s paper.
interest.

The easier PTAS is described in § 2. The EPTAS(Theorem 1.1) is given in § 3. The hardness proof(Theorem 1.2) can be found in § 4.
Further related work. Searching for approximation
schemes for NP-hard geometric optimization problems(or showing that they cannot exist) is a rich field of
research. Such schemes, while often impractical to
implement directly, have led both to new algorithmic
techniques and to a better structural understandingof the geometric problems. A full survey of such Fig. 1: Illustration of Lemma 2.1. The dashed edges canworks is out of scope here, we only mention a few replace {x, y} and {p, q} in the optimal tour.
representative or recent results [4, 28, 18, 5, 29, 22].
Open question. Our current work does not address
the complexity status of solving MSTSP in the
Euclidean plane exactly. It remains open whether
this problem is NP-hard (the fact that the problem isin NP is easy to see). We note that this question
has a natural equivalent formulation: Is checking
for existence of a Hamiltonian cycle NP-complete incomplements of unit disk graphs?
The complexity status of planar Euclidean
MaxTSP is similarly unresolved. For this problem
even the membership in NP is open, due to the issue
of precision in sums of square roots (see e.g. [27, § 3]).
2

Warmup: a simple PTAS

In this section we prove the following theorem.
To keep the analysis simple, we do not optimize
the involved constants, and we restrict attention to
Euclidean spaces.
Theorem 2.1. Let P be a set of n points in Rd . A
tour of P whose scatter is at least a (1−ε)factor of the
2 d

MSTSP optimum can be found in time O n(75d/ε ).

Consider a set P of n points in Rd , and a precisionparameter ε > 0. Observe that the MSTSP optimum(i. e., the shortest
 edge length of a tour of P ) can only
take one of n2 possible values (the distances between
points in P ). We sort the distances in decreasing order,and for each distance ` we attempt to construct a tour
with scatter `. Our procedure will either produce acertificate that no such tour exists (in which case we
continue with the next value of `), or it succeeds inconstructing a tour of P with scatter at least `(1 − ε).
Before proceeding to the algorithm, we present
a simple structural observation upon which thealgorithm relies. Suppose that ` is the maximum
value such that a tour T of P exists with scatter `,i. e., ` is the MSTSP optimum. Let p, q ∈ P be twoneighboring points in T , i. e., the edge {p, q} is partof T , such that d(p, q) = `. Let Bp and Bq denotethe open balls of radius `(1 + ε), with centers p and q,

respectively. We show that the optimal solution canbe assumed to have a certain structure in relation to
Bp and Bq .
Lemma 2.1. Let ` be the maximum value such thata tour T of P exists with scatter `. Then there is atour T 0 of P with scatter ` containing an edge {p, q}
with d(p, q) = `, such that for every edge {x, y} of T 0 ,at least one of x and y is contained in Bp ∪ Bq .
Proof. Let T be a tour of P with scatter `, let {p, q}
be an edge of T of length `, and let {x, y} be an edgeof T such that x, y ∈/ Bp ∪ Bq . By the definition of
Bp and Bq we have d(x, p), d(x, q), d(y, p), d(y, q) > `.
Thus, we can replace the edges {x, y} and {p, q} in
T , with either {x, p} and {y, q}, or {x, q} and {y, p},depending on the ordering of the points in T , suchas to preserve the connectedness of the tour. We
obtain another tour with scatter at least `, in which
the number of edges of length exactly ` has decreased.
If the obtained tour contains no edge of length `,then its scatter is strictly larger than `, contradicting
the choice of `. Otherwise, we repeat the argumentwith a remaining edge of length `. See Fig. 1 for an
illustration.
The next ingredient of the algorithm is a coarsening of the input, by rounding points in P to pointsof a grid. Let Gδ be a δ-scaling of the d-dimensional
unit grid, i. e., Gδ = {δ(n1 , . . . , nd ) | n1 , . . . , nd ∈ Z},
for an arbitrary δ > 0. Let fδ (·), or simply f (·), be
the function from Rd to Gδ that maps each point
to its nearest grid point (breaking ties arbitrarily).
The following properties result from basic geometricconsiderations.
Lemma 2.2. With f (·) and δ as defined earlier, we
have:√(i) d(x, y) ≥ d(f (x), y) − δ d/2 for all x, y ∈ Rd ,(ii) |B ∩ Gδ | ≤ (2`/δ + 1)d for every open ball B ofradius `.

Given a point set P ∈ Rd , let GP be a graph withvertex set V (GP ) = P and edge set
E(GP ) = {{x, y} | x, y ∈ P, d(x, y) ≥ `} .
In words, GP contains all edges with length atleast `. We wish to find a Hamiltonian cycle in GP
or show that there is none.
Observe that under f (·), the graph GP becomesa multigraph HP , with vertex set
V (HP ) = {v | v = f (x), x ∈ P },i. e., the set of grid points with at least one
mapped point of P , and edge set E(HP ) defined as{{u, v} | u = f (x), v = f (y), {x, y} ∈ E(GP )} ,i. e., the pairs of grid points to which edges of GP
are mapped. We also maintain multiplicities on edgesof HP , keeping track of how many edges of GP are
mapped to each edge of HP .
Consider a tour T of P of scatter at least `,i. e., a Hamiltonian cycle of GP . Under f (·), theedges of T form a spanning subgraph HP0 of HP (i. e.,
V (HP0 ) = V (HP )), and T is mapped to an Eulerian
tour of HP0 . It is not hard to see that given thisEulerian tour of HP0 , a tour of P can be recovered (byreplacing multiple occurrences of a grid point withthe points in P that are mapped to it). Moreover, thescatter of the recovered tour is not far from that of T
(by Lemma 2.2(i)). However, the edges of HP0 are notavailable to us, and guessing them seems prohibitively
expensive. The key idea is that it is sufficient toconsider the portion of HP that falls inside Bp ∪ Bq ,for points p and q chosen as in Lemma 2.1.

rounding (i. e., the approximation ratio) is controlled
by the choice of the grid resolution δ.
Algorithm A (PTAS).
Input: Set P of n points in Rd and a precisionparameter ε > 0.
Output: A value ` such that P admits a tour with
scatter at least `(1 − ε), and no tour with scatter
greater than `.
1. Iterate p, q over all pairs of points in P in
decreasing order of d(p, q).
√
2. Let ` = d(p, q). Let δ = ε`/(2 d). Let`0 = `(1 − ε/2).
Let Bp and Bq be the open balls with centers p
and q of radius `(1 + ε), and let B = Bp ∪ Bq .
3. Let f : P → Gδ map points to their nearest grid
point.
Compute the set C = {f (x) | x ∈ (P ∩ B)}, andthe sets f −1 (v) = {x | f (x) = v} for each v ∈ C.

4. Iterate over all functions m, v : C2 → N,such that for all {u, v} ⊆ C,0(i) m({u,X v}) = 0 if d(u, v) < ` , and(ii)m({u, v}) + v({u, v}) = 2|f −1 (v)|.
u∈C\{v}

If there are no more available functions, thenContinue from 1. (next pair p, q)
5. Construct a bipartite graph B as follows:- for each {u, v} ⊆ C, add v({u, v}) vertices
labeled {u, v} to the left vertex set L(B).
- for each x ∈ P \ B add a vertex labeled x to theright vertex set R(B).
- add edge ({u, v}, x) between {u, v} ∈ L(B) andx ∈ R(B) to E(B) iff d(u, x), d(v, x) ≥ `0 .
6. Find a perfect matching M of B; if there is none,
Continue from 4. (next m(·) and v(·)).
7. Construct a multigraph H as follows:- let V (H) = C ∪ (P \ B).
- for all {u, v} ⊆ C add m({u, v}) copies of theedge {u, v} to E(H).
- for all ({u, v}, x) ∈ M add the edges {u, x} and{v, x} to E(H).
8. Find an Eulerian tour Q of H; if there is none,
Continue from 4. (next m(·) and v(·)).
9. Transform Q into a tour T of P , by replacing
multiple occurrences of every point v ∈ C withthe points in f −1 (v) in arbitrary order.
10. Output ` and Stop.

We describe at a high level the approximation
algorithm (see algorithm A for the details, and Fig. 2
for an illustration). We assume that the optimal tour
T has the property from Lemma 2.1 with respect topoints p, q ∈ P , and that such p and q were “guessed”.
Let B = Bp ∪ Bq (recall that Bp and Bq have radius`(1 + ε).) Then, T consists of edges fully inside B, and“hops” of two consecutive edges, connecting a point
outside B with two points inside B. We replace suchhops with virtual edges, both of whose endpoints arein B. The resulting tour is entirely in B, and we can“guess” its image under fδ (·). This is now feasible,
since the number of grid points involved is boundedby Lemma 2.2(ii). We also guess the multiplicitiesof all edges, i. e., how many original edges have been
mapped to each edge, and how many edges are virtual.
We then disambiguate the virtual edges, findinga suitable midpoint outside of B for each hop. This isachieved by solving a perfect matching problem. We
obtain a multigraph on which we find an Eulerian
tour. Finally, from the Eulerian tour we recover Correctness. We prove two claims which together
a tour of P . The distortion in distances due to imply that algorithm A is a PTAS for MSTSP.

Lemma 2.3. If algorithm A outputs `, then there isa tour of P with scatter at least `(1 − ε).
Proof. If the value ` is returned in step 10, then steps
5–9 were successful with the current choice of p, q ∈ P
and the values of m(·) and v(·) chosen in step 4, andT is a tour of P . Consider an arbitrary edge {x, y} of
T . By step 9, there is a corresponding edge {u, v} inthe Eulerian tour Q of H. By construction of H instep 7, either (a) u, v ∈ C, or (b) ({u, w}, v) ∈ M or({v, w}, u) ∈ M , for some grid point w ∈ C.
In case (a) by condition (i) of step 4, we haved(u, v) ≥ `0 . Since {u, v} = {f (x),√f (y)}, from
Lemma 2.2(i) we obtain d(x, y) ≥ `0 − δ d = `(1 − ε).
In case (b) by the construction of B in step5, we have d(u, v) ≥ `0 . Since {u, v} equals either{f (x), y} or {x,√f (y)}, from Lemma 2.2(i) we obtaind(x, y) ≥ `0 − δ d/2 ≥ `(1 − ε).

M (T ) will be recovered in step 6. Observe thatany other perfect matching M of B corresponds toa shuffling of the points wi in B, and thus it is a
hop-matching of a tour T 0 in which the points wi havebeen correspondingly shuffled. T 0 differs from T onlyin its hops, and by construction of B√in step 5, we seethat T 0 has a scatter at least `0 − δ d/2 ≥ `(1 − ε).
It can be seen easily that the edges of T 0 are
mapped to an Eulerian tour of the multigraph H
constructed in step 7, and thus, step 8 succeeds. Again,
we cannot guarantee that the recovered Eulerian touris the same as the one to which T 0 maps. Every
Eulerian tour of H, however, has to respect the edgemultiplicities of H, which in turn are determined by
the number of points that map to each vertex of
H. Therefore, step 9 succeeds, and the output ` isreturned.

Running time. The main loop of step 1 represents
Lemma 2.4. If there is a tour of P with scatter `, a factor of O(n2 ) in the running time. The cost ofthen algorithm A outputs a value of at least `.
steps 2–3 is dominated by the cost of the inner loopthat starts in step 4.
Proof. Assume that a tour T of P of scatter ` exists.
We need to bound |C|, the number of grid points
Observe that the main loop (step 1) considers pairs
inside B to which some point of P is mapped. Byp, q in the decreasing order of their distance. If a
Lemma 2.2(i) all such grid points are inside one of√ thevalue greater than ` is returned, we are done. Assume
balls with center p and q, with radius ` + ε + δ d/2.
therefore, that we are in the case where d(p, q) = `.
By Lemma 2.2(ii) we have
Assume also w. l. o. g. that T has the special!d√structure described in Lemma 2.1 with respect to
d
2`
+
2ε`
+
δ
p and q, i. e., it consists of hops and of edges entirely|C| ≤ 2 ·+1δinside B = Bp ∪ Bq . Consider an edge {x, y} of T ,√√such that x, y ∈ B. Then, after step 3, f (x), f (y) ∈ C= 2 · (4 d/ε + 5 d + 1)dholds, and we say that {x, y} maps to {f (x), f (y)}.
√≤ 2 · (5 d/ε)d .
Consider now a hop of T , i. e., two consecutive edges{x, w} and {w, y}, such that x, y ∈ B and w ∈ P \ B.
(In the last inequality we assume ε ≤ 1/5.)
Then, after step 3, f (x), f (y) ∈ C holds, and we say
Steps 5 and 6 amount to finding a bipartitethat the hop {x, w, y} virtually maps to {f (x), f (y)}.
perfect
matching, and steps 7 and 8 amount toConsider now the inner loop (step 4). Let∗
findinganEulerian tour, both in a graph with O(n)m ({u, v}) be the number of edges in T that map∗
vertices.
These
steps can be executed in time O(n2.5 ),to {u, v}, and let v ({u, v}) be the number of hops in2
T that virtually map to {u, v}. Since every point respectively O(n ) using textbook algorithms.
As for step 4, observe that the values of m(·) andin T has degree 2, it follows that the number ofv(·)
over all pairs in C sum to |P ∩ B| ≤ n, so weedges and hops mapped to an edge incident to somenneed
to consider at most |C|ways of distributing a2u ∈ C is twice the number of points in P mapped
value
of
at
most
n
into
the
integervalues of m andto u. Furthermore, for all√edges {x, y} ⊆ B of T , we
0v.
Multiplying,
and
using
a
standard
bound on thehave d(f (x), f (y)) ≥ ` − δ d = ` (by Lemma 2.2(i)).
∗
binomial
coefficient,weobtainthat
theTherefore, choosing the correct functions m = m andrunning time∗
|C|2 +3+2(75d/ε2 )dv = v is consistent with the conditions in step 4.
is at most O(n)O n.
Let {x1 , w1 , y1 }, . . . , {xk , wk , yk } denote all the
hops in T , where wi ∈ P \ B, for all i. Let
Note. The restrictions on m(·) and v(·) in step
u
=
f
(x
),
and
v
=
f
(y
),
and
let
us
call
M
(T
)
=
4
of
algorithm A can be strengthened, resulting
i
i
i
i


{ui , vi }, wi | i = 1, . . . , k the hop-matching of T . in a smaller number of iterations (and thus better
Observe that M (T ) is a valid perfect matching for running time). For instance, since each virtual edge
the graph B constructed in step 5, therefore, step 6 corresponds to a hop via a point outside of B, wewill succeed. We cannot, however, guarantee that could require the values of v(·) to sum to |P \ B|. We

Fig. 2: Illustration of algorithm A. (i) Input point set with open balls Bp and Bq with centers p and q and radius`(1 + ε). (ii) Points inside Bp ∪ Bq mapped to grid points (shown as squares), and “guessed” edges. Filled squares
indicate grid points to which more than one point is mapped. Dotted lines indicate virtual edges, and the number
indicates the multiplicity of an edge (omitted if 1). (iii) Virtual edges matched to points outside of Bp ∪ Bq andextended to hops, resulting in a multigraph. (iv) An Eulerian tour of the multigraph, expanded to a tour on the initialpoint set.

ignore such technicalities, as they do not affect thecorrectness of algorithm A – in the case of wrong
values, we break out of the loop in some of the later
steps.

Lemma 3.1. (Dirac’s theorem) A graph G with nvertices has a Hamiltonian cycle if the degree of every
vertex in G is at least n2 . Furthermore, in such a case,a Hamiltonian cycle can be found in O(n2 ) time.

3

Lemma 3.2. (Bondy-Chvátal theorem) Let
G = G0 be a graph with n vertices, and let G1 , . . . , Gk
be a sequence of graphs. For all i, the graph Gi
is obtained from Gi−1 by adding an edge between
some pair of vertices whose total degree in Gi−1 isat least n. The graph Gk is Hamiltonian if and only
if G is Hamiltonian. Furthermore, given Gk and a
Hamiltonian cycle of Gk , a Hamiltonian cycle of G
can be found in O(n3 ) time.

The main result: an EPTASIn this section we strengthen the result of § 2 andprove Theorem 1.1.
Let D be a doubling space with metric d(·), andlet d denote the doubling dimension of D. Let P
be a set of n points in D. Suppose we are givena threshold value ` > 0, together with a precisionparameter ε > 0. Given these inputs, we seek anapproximation for the decision version of MSTSP:
With running time polynomial in n, our algorithm
Let GP denote the graph over P containing
returns Yes if a tour of P exists with scatter at least `, all edges with length at least `, similarly as in § 3.
and returns No if there is no tour of P with scatter at Observe that if the condition of Dirac’s theorem
least `(1−ε). If neither of the two conditions hold, the (Lemma 3.1) holds for G , then we are done. InPalgorithm is allowed to return Yes or No arbitrarily. the following, we assume that this is not the case.
Since the optimum value of an MSTSP instance can Hence, there is a vertex in G whose degree is lessP
only take one of the n2 possible distances, we can than n . In other words, there is a point p ∈ P , such2
turn an approximation of the above kind into an that |B ∩ P | > n , where B is the open ball of radiusppapproximation for the optimization problem with a ` with center p.2 Let us fix p to be such a point,
simple binary search, at the cost of an O(log n)-factor and let B and B 0 denote the open balls of radius `,pp
in the running time. In the following, we focus only resp. 2` with center p. We make a simple structuralon the decision problem.
observation similar to Lemma 2.1.
We start by presenting the main tools that we
use in our algorithm.
Lemma 3.3. Suppose a tour T of P with scatter at
The following two graph-theoretic results are well- least ` exists. Then there exists a tour T 0 of P withknown (see e. g., [10]). Dirac’s theorem (Lemma 3.1) scatter at least `, such that for every pair x, y ∈ P of
was also used by Arkin et al. to get a 0.5- neighboring points in T 0 , at least one of x and y isapproximation for metric MSTSP. The Bondy-Chvátal contained in Bp0 .
theorem (Lemma 3.2, [11]) is a generalization ofLemma 3.1. The classical proofs of both results are Proof. Suppose this is not the case. Since Bp contains
implicitly algorithmic.
more than half of the points in P , it has to containat least one edge of T entirely. Let {z, t} be suchConsider a set of points in D. We call a point
set RP in D an ε-net of P , if the balls of radius εcentered at the points in RP cover P . Given an ε-net
RP of P , we define a function f (·) that maps every
point in P to the nearest point in RP . We state thefollowing.
Lemma 3.5. Given an open ball B of radius ` in inD, δ > 0, and a point set P ⊂ B, we can find a
δ-net R of P , in deterministic O(|P |2 ) time, with thefollowing properties.
Fig. 3: Illustration of Lemma 3.3. The dashed edges can(i) d(x, y) ≥ d(f (x), y) − δ for all x, y ∈ R.
dreplace {x, y} and {z, t} in the optimal tour.
(ii) |R| ≤ 2`/δ + 1 .
Proof. Part (i) follows from the definition of a δ-net.
We construct R greedily by repeatedly picking an
unmarked point in P , adding it to R, and marking
it, together with all points in P that are at distanceat most δ from the picked point, until all points in P
are marked. We observe that the balls of radius δ/2centered at the points in R are disjoint and containedin a ball of radius ` + δ/2. By the fact that the sizeof a packing is at most the size of the minimum cover,dand observing that 2`/δ + 1 balls of radius δ/2 cancover an arbitrary ball of radius ` + δ/2, we obtain the
The next tool we use is an efficient algorithm
bound of part (ii). In the last step we repeatedly apply
for the many-visits variant of TSP, found in 1984 by
the bound from the definition of a metric space with
Cosmadakis and Papadimitriou [14]. We state thedoubling dimension d, and we assume for simplicity
result in the following variant.
that 2`/δ + 1 is a power of two.
Lemma 3.4. (Many-visits TSP) Given a graph G
We are ready to present the algorithm. Consider
with vertices v1 , . . . , vk , and integers n1 , . . . , nk > 0,aset
P of points in D, a threshold value `, and athere is an algorithm CP that finds a tour of G thatprecision
parameter ε > 0. We solve the approximate
visits vertex vi exactly ni times, for all i, or reports
decision
problem
described above. Recall that GP isthat no such tour exists.
the
graph
over
P
,
containing the edges with length at
3
The running time of algorithm CP is O n + k ·Pleast `.
O(k log k)log n + 2
, where n = ni .
Call a point p ∈ P low-degree, if |Bp ∩ P | > n2 ,Lemma 3.4 is shown by Cosmadakis and Papadim- where Bp = B1 is the open ball of radius ` with center
itriou in the variant where G is the complete graph, p. If no such point exists, we are done, by Lemma 3.1.
and for arbitrary given edge-weights the shortest tour Let B2 be an open ball of radius 2` with a low-degree
is to be found (respecting the given multiplicities ni ). point p at its center. Observe that all low-degree
To obtain the statement in Lemma 3.4 it is sufficient points are contained in B2 . Suppose otherwise thatto choose suitable edge-weights, e. g., the values 1 and there is a low-degree point q outside of B2 . Then the
2 for wanted, resp. unwanted edges. We then need balls Bp and Bq are disjoint and contain more thanto check
P whether the length of the shortest tour is at n points in total, a contradiction. (A stronger boundmostni , i. e., whether a tour exists that uses only on the radius of B2 can be shown, as a function of d,weight-one edges.
but the value of 2` is sufficient for our purposes.) Let
In its original form, algorithm CP returns only B3 denote the open ball of radius 3` having the samethe multiplicities of edges in the solution, not the tour center as B2 .
itself. We can find a tour with the obtained edgeAlgorithm B uses a similar rounding approach
multiplicities by computinganEulerian
tour,
with
as
algorithm
A. We first sketch the main idea, thenP 
running time O
ni . We refer to [14] for more present the details of the algorithm.
precise bounds on the running time.
Finally, we replace the grid-cover used in § 2 by
We wish to find a tour of P (i. e., a Hamiltonianan ε-net with stronger properties.
cycle of GP ). Given B2 and B3 as described above,
an edge. Since both x and y are outside of Bp0 wehave d(x, t), d(x, z), d(y, t), d(y, z) ≥ `. Thus, we canreplace the edges {x, y} and {z, t} in T , with either{x, z} and {y, t}, or {x, t} and {y, z}, depending on
the ordering of the points in T , such as to preserve
the connectedness of the tour. We obtain anothertour with scatter at least `, that no longer contains
the edge {x, y}. We proceed in the same way until wehave removed all edges with both endpoints outsideof Bp0 . See Fig. 3 for an illustration.

and using Lemma 3.2, we can augment GP with alledges among points outside B2 (since these are all
high-degree points). Furthermore, observe that everyedge between a point outside B3 and a point inside
B2 is already present (since the distance between such
points is at least `). Thus, every point outside of B3
can be assumed to be connected to every point in P .
We can therefore collapse every point in P \ B3 to asingle “virtual point” and focus only on the portionof the tour that falls inside B3 .
Similarly to algorithm A, we can round points
inside B3 to grid points (in this case, to a δ-net).
Since we no longer have the issue of hops fromalgorithm A, the problem that remains to be solved
is simply the many-visits TSP described in Lemma 3.4.
Algorithm B (EPTAS).
Input: Set P of n points in D, a threshold `, and a
precision parameter ε > 0.
Output: Yes, if P admits a tour with scatter at
least `, and No if P does not admit a tour with
scatter at least `(1 − ε).
1. Let δ = ε`/2.
2. Find a low-degree point p ∈ P , and let B2 resp.
B3 be the open balls with center p and radius 2`
resp. 3`. If no such p exists, output Yes.
3. Find the δ-net R of P ∩ B3 by the algorithm ofLemma 3.5, and let f : (P ∩ B3 ) → R map points
to their nearest point in R. For each v ∈ R,
compute the sets f −1 (v) = {x | f (x) = v}.
4. Construct a graph G0 as follows:- let V (G0 ) = R ∪ {q}.
- for all {u, v} ⊆ R add edge {u, v} to E(G0 ) iffd(u, v) ≥ `.
- for all u ∈ R add edge {q, u} to E(G0 ).
5. Let nv = |f −1 (v)| for every v ∈ R, and let
nq = n − |P ∩ B3 |.

Correctness. Again, we proceed via two separate
claims.
Lemma 3.6. If algorithm B outputs Yes, then there
is a tour of P with scatter at least `(1 − ε).
Proof. If we obtain Yes in step 2, then by Lemma 3.1
there is a tour of P with scatter at least `. Supposethat we obtain Yes in step 9 and thus steps 1–8
execute successfully. Let G0P be the graph over P withall edges with length at least `(1 − ε). We wish toshow that G0P is Hamiltonian. Since step 6 succeeds, amany-visits tour of the graph G0 constructed in step 4
is found. Since the number of visits in each vertex
equals the number of points from P mapped to thatvertex, in step 7 we successfully recover a tour T ofP.
We wish to show that tour T is a Hamiltonian
tour of some graph G∗P that can be obtained from
G0P by repeatedly connecting pairs of vertices whose
sum of degrees is at least n (see Lemma 3.2). Then,the existence of a Hamiltonian cycle in G0P follows by
Lemma 3.2 from the existence of a Hamiltonian cyclein G∗P .
In T there are two types of edges: (a) edges
between points inside of B3 , and (b) edges between apoint inside B3 and a point outside of B3 . Observethat there are no edges between two points outsideof B3 , since all points outside of B3 were mapped tothe same vertex q, and we had no self-edges in G0 .
Consider an arbitrary edge {x, y} of T . We need toshow that d(x, y) ≥ `(1 − ε). Suppose that {x, y}
is of type (a). By the construction of G0 it follows
that d(f (x), f (y)) ≥ `, and by Lemma 3.5(i) it follows
that d(x, y) ≥ ` − 2δ = `(1 − ε). Suppose now that{x, y} is of type (b), and x ∈/ B3 . If y ∈ B2 , thenclearly d(x, y) ≥ `. Otherwise, if y ∈/ B2 , then bothx and y are high-degree points (since B2 contains
all low-degree points), and thus the sum of theirdegrees in G0P is at least n, therefore G0P can safely
be augmented with the edge {x, y}, without affecting
its Hamiltonicity.

6. Using algorithm CP (Lemma 3.4), find a manyvisits tour Q of G0 with multiplicities nv for every Lemma 3.7. If there is a tour of P with scatter at
least `, then algorithm B outputs Yes.
v ∈ V (G0 ); if there is none, output No.
7. Transform Q into a tour T of P , by replacing
multiple occurrences of every point v ∈ R withthe points in f −1 (v) in arbitrary order, and by
replacing occurrences of q with the points in
P \ B3 in arbitrary order.

Proof. Suppose there exists a tour T ∗ of P with
scatter at least ` (i. e., a Hamiltonian cycle of GP ). If
there is no low-degree point, step 2 correctly outputs
Yes. Otherwise B2 is centered at a low-degree point
and therefore we can assume that T ∗ has the hop8. Transform T into a tour of GP by the algorithm structure described in Lemma 3.3 with respect toof Lemma 3.2.
B2 . In words, there are no edges of T ∗ with both
endpoints outside of B2 . Then, it is easy to check that
9. Output Yes.
in steps 3,4 and 5, f (·) maps T ∗ to a many-visits TSP

of the constructed graph G0 , matching the required
multiplicities. Therefore, step 6 succeeds. Step 7
always succeeds, but the resulting tour T may not be
the same as T ∗ . In particular, T might have shortedges that are not contained in GP , nonetheless, they
are contained in an augmentation of GP as describedin part (1), therefore step 8 succeeds.
Running time. The costs of step 6 and step 8
dominate the overall running time. The running
time of these steps can be bounded using Lemma 3.4,
respectively Lemma 3.2, obtaining the total running
time O(n3 + 2O(k log k) + k 3 · log n), where k = |R|.
dUsing Lemma 3.5(ii), we obtain k ≤ 6`≤
δ +1
(13/ε)d , finishing the proof.
4

Hardness in high-dimensional Euclidean
spacesTrevisan [36] showed that the standard TSP
is APX-hard in the log n-dimensional space Rlog n ,where the distances are computed with respect toan arbitrary `p norm. The main ingredient of his
proof is an embedding of graphs with edge costs in{1, 2} into Rlog n . The embedding is done by assigningbinary vectors as labels to the vertices, such that theHamming distance between two vertex-labels is D1 if
the edge between the respective vertices has cost one,and D2 otherwise. The values of D1 and D2 differ by
a constant factor.
The proof relies on the fact that there is a value
B0 such that TSP with edge costs {1, 2} is APX-hard,even if each vertex is incident to at most B0 cost-one
edges.
The natural idea to adapt Trevisan’s result to
MSTSP is to invert the graph: each edge of cost one
becomes an edge of cost two and vice versa. In the
new graph, however, the previously used encoding ofvertices is not suitable anymore. Instead of decreasing
the Hamming distance of vectors in the case of costone edges, now we have to increase the Hamming
distance in case of cost-two edges. Our proof uses
the general outline of Trevisan’s result, but differs incertain details.
We first show the hardness of approximating
MSTSP in O(2n )-dimensional Hamming spaces. The
nature of MSTSP allows us to use a gap-introducing
reduction instead of an approximation-preserving
reduction. Akiyama et al. [1] showed that it is NPhard to decide whether a bipartite 3-regular graph has
a Hamiltonian cycle. Given such a graph, we associatenwith each vertex a vector from {0, 1}3·2 , and consider
the edge costs to be the Hamming distance between
vertices (i. e., the number of positions where the two
vectors are distinct).

For the reduction we use first-order Reed-Muller
codes and their complements. A first-order Reedn
Muller code Hn ⊂ {0, 1}2 is a set of n vectors oflength 2n such that the pairwise Hamming distance of
two code-words is exactly 2n /2. The complement ū ofna code-word u is 12 − u, i. e., we invert each entry ofu. Note that the Hamming distance of u and ū is 2n ,but for all u0 ∈ Hn , u0 6= u, the Hamming distance ofū and u0 is 2n /2. Let H̄n be the code that for each
vector u ∈ Hn contains the vector ū.
Let G be a bipartite 3-regular graph with nvertices. It is well-known that such a graph has a
3-edge coloring that can be found efficiently. Consider
such an edge-coloring. We fix an ordering of the edgesof G of the same color, and refer to the kth edge ofcolor i for 1 ≤ k ≤ n and 1 ≤ i ≤ 3.
To each vertex of G we assign a binary vector oflength 3 · 2n . The first 2n entries belong to the firstcolor, the second 2n entries to the second color, andthe third 2n entries to the third color.
Let e = {u, v} be the kth edge of color i. Then
we set the ith 2n entries of u to the kth code-word aof Hn , and we set the ith 2n entries of v to ā. It does
not matter which of the two vertices obtains which of
the two code-words.
Lemma 4.1. Let u, v be two vertices of G, and let dH
be the Hamming distance between the vertices (i. e.,
3 · 2n -vectors).
1. If {u, v} ∈ E(G), then dH (u, v) = 2 · 2n ; and2. if {u, v} ∈/ E(G), then dH (u, v) = 3 · 2n /2.
Proof. If e = {u, v} ∈ E(G), there is a k and an isuch that e is the kth edge of color i, and therefore
all of the ith 2n entries of u and v disagree. For thetwo remaining colors, there is no edge between u andv, and therefore each of the two remaining pairs ofvectors disagree in exactly 2n /2 entries: All codewords are from Hn or H̄n , and none of the two pairs
has complementary code-words. If {u, v} ∈/ E(G),
then the Hamming distance between each pair ofvectors is exactly 2n /2 and thus the overall distanceis 3 · 2n /2.
The lemma implies that it is NP-hard to obtaina (3/4 + ε)-approximation for MSTSP in 3 · 2n dimensional Hamming metrics. Suppose otherwisethat a polynomial-time algorithm A can compute suchan approximation. Then, given a hard instance G,
and the vertex-labeling described above, we conclude
that G is Hamiltonian if and only if it admits atour with scatter 2n+1 (w.r.t. the Hamming-distances
between vertex-labels). If there is no such tour, thenthe optimal MSTSP solution has value 3 · 2n /2 <(3/4 + ε) · 2n+1 . We can therefore use A to decide the
Hamiltonicity of G in polynomial time.

We still have the problem that the dimension
3 · 2n is too large. To obtain a suitable embedding,we have to accept a small error. We say that anembedding f : V × V → {0, 1}k is (k, D1 , D2 , γ)-good
if for u, v ∈ V ,1. if {u, v} is of cost 1, then D1 − γ ≤dH (f (u), f (v)) ≤ D1 + γ; and2. if {u, v} is of cost 2, then D2 − γ ≤dH (f (u), f (v)) ≤ D2 + γ.
Lemma 4.2. (Naor, Naor [30], Trevisan [36])For every ε > 0 and positive integer n there
is a collection Cn,ε ⊆ {0, 1}k(n,ε) such that|Cn,ε | = n, k(n, ε) = O((log n)/poly(1/ε)), andfor each pair of two elements u, v ∈ Cn,ε we havek(n, ε)(1/2 − ε) ≤ dH (u, v) ≤ k(n, ε)(1/2 + ε).
Furthermore, there is a procedure that computes Cn,εin poly(n, 1/ε) time.
Observe that inverting a code-word only changes thesign of the error. We can therefore apply the previous
results with respect to the smaller code-words andobtain the following.
Lemma 4.3. Let G be a complete n-vertex graph withedge costs in {1, 2} such that the induced subgraph ofthe cost-two edges is bipartite and 3-regular. Thereis a polynomial-time algorithm that, for an arbitrary
γ > 0, finds a (k, 3D/2, 2D, γ)-goodembedding of
V (G), where k = O log(3n)/γ 2 and D = k/2.
Theorem 4.1. There is a constant c such that it is
NP-hard to obtain a (3/4)1/p -approximate solution to
MSTSP in Rd for d ≥ c log n and distances according
to the `p norm.
Theorem 4.1 follows from the previous discussion and using that for u, v ∈ {0, 1}n , dp (u, v) =dH (u, v)1/p , where dp is the distance according to `p norm. Note that {0, 1}n ⊆ Rn and we can interpretu and v as vectors in the Euclidean space.
For large d, the running time of algorithm B isdominated by the term 2K log K , where K = (13/ε)d .
The APX-hardness in the c log n-dimensional Euclidean space shows that, except for minor terms,
according to our current knowledge, this running
time cannot be improved with respect to d: Anoε (d)
approximation scheme with running time 22
would imply that we can solve the Hamiltonian
cycle problem in bipartite 3-regular graphs in time
2o(n) . We observe that the reduction from 3-SAT
to Hamiltonian cycle in the target class of graphs
increases the parameters only linearly, therefore it
preserves subexponential time. (We refer to thehardness proof in [1], and the additional details in [19].

We remark, that, since we do not require planarity,
the step of removing crossings is not required.) Hence,the existence of such an approximation scheme
would contradict the exponential time hypothesis(ETH) [23] and Theorem 1.2 follows.
We leave open the question of whether the
dependence on ε can be improved, and whether
there exist more efficient approximation schemes
specifically tailored to the low-dimensional case.
Acknowledgment. We would like to thank Karteek
Sreenivasaiah for several helpful discussions, and theanonymous reviewers for thoughtful comments.
References[1] Takanori Akiyama, Takao Nishizeki, and Nobuji
Saito. NP-completeness of the Hamiltonian cycle
problem for bipartite graphs. Journal of Information
Processing, 3(2):73–76, 1980.
[2] Esther M. Arkin, Yi-Jen Chiang, Joseph S. B.
Mitchell, Steven Skiena, and Tae-Cheon Yang. On
the maximum scatter traveling salesperson problem.
SIAM J. Comput., 29(2):515–544, 1999.
[3] Esther M. Arkin, Yi-Jen Chiang, Joseph S. B.
Mitchell, Steven S. Skiena, and Tae-Cheon Yang.
On the maximum scatter TSP. In Proceedings of theEighth Annual ACM-SIAM Symposium on Discrete
Algorithms, SODA ’97, pages 211–220, Philadelphia,
PA, USA, 1997. Society for Industrial and Applied
Mathematics.
[4] Sanjeev Arora. Polynomial time approximation
schemes for euclidean traveling salesman and othergeometric problems. J. ACM, 45(5):753–782, 1998.
[5] Sunil Arya and David M. Mount. A fast and simple
algorithm for computing approximate euclidean
minimum spanning trees. In Proceedings of theTwenty-Seventh Annual ACM-SIAM Symposium on
Discrete Algorithms, SODA ’16, pages 1220–1233,
Philadelphia, PA, USA, 2016. Society for Industrial
and Applied Mathematics.
[6] Yair Bartal and Lee-Ad Gottlieb. A linear time
approximation scheme for euclidean TSP. In Proceedings of the 54th Annual IEEE Symposium on
Foundations of Computer Science, FOCS ’13, pages
698–706, 2013.
[7] Yair Bartal, Lee-Ad Gottlieb, and Robert
Krauthgamer. The traveling salesman problem: Lowdimensionality implies a polynomial time approximation scheme. SIAM J. Comput., 45(4):1563–1581,
2016.
[8] Alexander I. Barvinok. Two algorithmic results forthe traveling salesman problem. Math. Oper. Res.,
21(1):65–84, 1996.
[9] Alexander I. Barvinok, Sándor P. Fekete, David S.
Johnson, Arie Tamir, Gerhard J. Woeginger, andRussell Wodroofe. The geometric maximum travelingsalesman problem. J. ACM, 50:641–664, 2003.
[10] Béla Bollobás. Modern Graph Theory. Springer,
1998.
[11] J. A. Bondy and V. Chvatal. A method in graphtheory. Discrete Math., 15(2):111–135, January 1976.
[12] Nicos Christofides. Worst-case analysis of a new
heuristic for the travelling salesman problem. Technical Report 388, Carnegie Mellon University, 1976.
[13] L. K. Clarkson. Nearest neighbor queries in metric spaces. Discrete & Computational Geometry,
22(1):63–93, 1999.
[14] Stavros S. Cosmadakis and Christos H. Papadimitriou. The traveling salesman problem with many
visits to few cities. SIAM J. Comput., 13(1):99–108,
1984.
[15] E. D. Demaine, J. S. B. Mitchell, andJ. O’Rourke. The open problems project. Available:
http://cs.smith.edu/˜orourke/TOPP/.
[16] N. N. Doroshko and V. I. Sarvanov. The minimax
traveling salesman problem and hamiltonian cycles
in powers of graphs (Russian). Vestsi Akad. Navuk
BSSR, Ser. Fiz.-Mat. Navuk, 143(6):119–120, 1981.
[17] Sándor P. Fekete. Simplicity and hardness of the
maximum traveling salesman problem under geometric distances. In Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms,
SODA ’99, pages 337–345. ACM/SIAM, 1999.
[18] Zachary Friggstad, Mohsen Rezapour, and Mohammad R. Salavatipour. Local search yields a PTAS
for k-means in doubling metrics. In Proceedings of
the 57th Annual IEEE Symposium on Foundationsof Computer Science, FOCS ’16. IEEE Computer
Society, 2016.
[19] M. R. Garey, D. S. Johnson, and R. Endre Tarjan. The planar hamiltonian circuit problem is npcomplete. SIAM Journal on Computing, 5(4):704–
714, 1976.
[20] Anupam Gupta, Robert Krauthgamer, and James R.
Lee.
Bounded geometries, fractals, and lowdistortion embeddings. In Proceedings of the 44th
Annual IEEE Symposium on Foundations of Computer Science, FOCS ’03, pages 534–543, Washington,
DC, USA, 2003. IEEE Computer Society.
[21] Gregory Gutin, Abraham Punnen, Alexander Barvinok, Edward Kh. Gimadi, and Anatoliy I. Serdyukov.
The Traveling Salesman Problem and Its Variations.
Springer, 2002.
[22] Sariel Har-Peled. Geometric Approximation Algorithms. American Mathematical Society, Boston,
MA, USA, 2011.
[23] Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential
complexity? Journal of Computer and System Sciences, 63(4):512 – 530, 2001.
[24] Marek Karpinski, Michael Lampis, and Richard
Schmied. New inapproximability bounds for TSP. J.
Comput. Syst. Sci., 81(8):1665–1677, 2015.
[25] Lukasz Kowalik and Marcin Mucha. Deterministic

7/8-approximation for the metric maximum TSP.
Theoretical Computer Science, 410(4749):5000 – 5009,
2009.
[26] John Larusic, Abraham P. Punnen, and Eric Aubanel.
Experimental analysis of heuristics for the bottleneck
traveling salesman problem. Journal of Heuristics,
18(3):473–503, June 2012.
[27] E.L. Lawler, D.B. Shmoys, A.H.G.R. Kan, and J.K.
Lenstra. The Traveling Salesman Problem. John
Wiley & Sons, 1985.
[28] Joseph S. B. Mitchell. Guillotine subdivisions approximate polygonal subdivisions: A simple polynomialtime approximation scheme for geometric TSP, kMST, and related problems. SIAM J. Comput,
28:402–408, 1996.
[29] Nabil H. Mustafa and Saurabh Ray. PTAS for
geometric hitting set problems via local search.
In Proceedings of the 25th ACM Symposium on
Computational Geometry, Aarhus, Denmark, June
8-10, 2009, pages 17–22, 2009.
[30] Joseph Naor and Moni Naor. Small-bias probability
spaces: Efficient constructions and applications.
SIAM J. Comput., 22(4):838–856, 1993.
[31] Christos H. Papadimitriou and Mihalis Yannakakis.
The traveling salesman problem with distances one
and two. Math. Oper. Res., 18(1):1–11, February
1993.
[32] R.Gary Parker and Ronald L Rardin. Guaranteedperformance heuristics for the bottleneck travelling
salesman problem. Oper. Res. Lett., 2(6):269–272,
March 1984.
[33] J.-R. Sack and J. Urrutia, editors. Handbook ofComputational Geometry. North-Holland PublishingCo., 2000.
[34] V. I. Sarvanov. A minimax traveling salesman
problem on a plane: complexity of an approximate
solution. (Russian). Dokl. Akad. Nauk Belarusi,
39(6):16–19, 1995.
[35] Kunal Talwar. Bypassing the embedding: Algorithms for low dimensional metrics. In Proceedingsof the Thirty-sixth Annual ACM Symposium on Theory of Computing, STOC ’04, pages 281–290, New
York, NY, USA, 2004. ACM.
[36] Luca Trevisan. When Hamming meets Euclid: The
approximability of geometric TSP and Steiner tree.
SIAM J. Comput., 30(2):475–485, April 2000.