<p>One such approach is to totally order the points of <span class="math-container">$\mathbb{R}^d$</span> by a space-filling curve (such as the <span class="math-container">$d$</span>-dimensional Hilbert curve), as proposed by Bartholdi and Platzman. Given finite <span class="math-container">$G$</span>, you simply visit its points in curve order. If you add a point to <span class="math-container">$G$</span>, you simply insert it in the tour (two new edges).</p>
<p>For <span class="math-container">$n$</span> points in the unit cube this yields a tour of length <span class="math-container">$O(n^{1-1/d})$</span>. In <span class="math-container">$\mathbb{R}^2$</span>, the tour length is <span class="math-container">$O(\lg n)\cdot\mbox{OPT}$</span>.</p>

CC BY-SA 4.0
2023-10-13T20:55:01.587Z
2023-10-13T20:55:01.587Z
mic
<p>I think I understand the spirit of what you are asking, but it is difficult to answer without a clear, rigorous question. Perhaps something along the following lines:</p>
<p>Given a set <span class="math-container">$V$</span> of <span class="math-container">$n$</span> points in <span class="math-container">$\mathbb{R}^d$</span>, an <span class="math-container">$(\alpha,k)$</span>-<em>robust tour</em> is a Hamiltonian cycle <span class="math-container">$T$</span> through <span class="math-container">$V$</span> such that:</p>
<ol>
<li><span class="math-container">$\text{length}(T) \leq \alpha\cdot\text{length}(T^*)$</span> where <span class="math-container">$T^*$</span> is a Hamiltonian cycle through <span class="math-container">$V$</span> of minimum length.</li>
<li>For any <span class="math-container">$x \in \mathbb{R}^d$</span>, there exists a Hamiltonian cycle <span class="math-container">$T'$</span> through <span class="math-container">$V\cup\{x\}$</span> such that <span class="math-container">$|T' \setminus T| \leq k+2$</span> and <span class="math-container">$\text{length}(T') \leq \alpha\cdot\text{length}(T^{**})$</span> where <span class="math-container">$T^{**}$</span> is a Hamiltonian cycle through <span class="math-container">$V\cup\{x\}$</span> of minimum length.</li>
</ol>
<p>Anyway, I am unaware of anything like this being studied, but you might want to poke around searching for &quot;robust combinatorial optimization&quot;.</p>

CC BY-SA 4.0
2023-10-06T23:31:29.083Z
2023-10-06T23:31:29.083Z
NaturalLogZ
<p>This, technically, answers the question as posted and is a bit large for a comment, so here it is.</p>
<blockquote>
<ol>
<li><p>Compute any <span class="math-container">$c$</span>-approximate TSP solution <span class="math-container">$P$</span> for <span class="math-container">$G$</span>.</p>
</li>
<li><p>Assume WLOG by renaming that <span class="math-container">$P=(x_1, x_2, \ldots, x_n)$</span>.</p>
</li>
<li><p>Let <span class="math-container">$x_i$</span> be the nearest neighbor of <span class="math-container">$x_{n+1}$</span>.</p>
</li>
<li><p>Return the tour <span class="math-container">$P^*=(x_1, x_2, .., x_i, x_{n+1}, x_{i+1}, x_{i+2}, ..., x_n)$</span> obtained by inserting <span class="math-container">$x_{n+1}$</span> into <span class="math-container">$P$</span> after <span class="math-container">$x_i$</span>.</p>
</li>
</ol>
</blockquote>
<p>The path <span class="math-container">$P^*$</span> differs from <span class="math-container">$P$</span> in three edges.  Assuming the underlying space is metric (as Euclidean spaces are), the cost of <span class="math-container">$P^*$</span> is at most the cost of <span class="math-container">$P$</span> plus <span class="math-container">$2 d(x_i, x_{n+1})$</span>. By the choice of <span class="math-container">$P$</span> and <span class="math-container">$i$</span> this is at most <span class="math-container">$c+2$</span> times the cost of an optimal path for <span class="math-container">$G^*$</span>.</p>
<p>No doubt one can do better.</p>

CC BY-SA 4.0
2023-11-15T22:03:46.983Z
2023-11-15T22:26:13.110Z
2023-11-15T22:26:13.110Z
Neal Young
<p>I was wondering if there are TSP approximations that are &quot;stable&quot;. More specifically, consider the set <span class="math-container">$G = x_1, ..., x_n$</span> and the set <span class="math-container">$G^* = G \cup x_{n+1}$</span>, where <span class="math-container">$x_i$</span> are points in <span class="math-container">$R^d$</span>. I was wondering if there are algorithms that approximate some sort of TSP on set <span class="math-container">$G$</span> and <span class="math-container">$G^*$</span> such that their edge sets are somewhat similar or differ by some constant number?</p>
<p>In short, I was wondering if anyone knew any TSP approximations that are robust in terms of the edge sets they determine.</p>

<graph-theory><approximation-algorithms>
Stable/Robust Traveling Salesman Approximation Methods
Winky
# Stable/Robust Traveling Salesman Approximation Methods

(Asked by: username_0 on 2023-10-06)

I was wondering if there are TSP approximations that are "stable". More specifically, consider the set $G = x\_1, ..., x\_n$ and the set $G^\* = G \cup x\_{n+1}$, where $x\_i$ are points in $R^d$. I was wondering if there are algorithms that approximate some sort of TSP on set $G$ and $G^\*$ such that their edge sets are somewhat similar or differ by some constant number?

In short, I was wondering if anyone knew any TSP approximations that are robust in terms of the edge sets they determine.

**Tags:** graph-theory, approximation-algorithms

---

## 3 answers

### Answer by username_1 on 2023-10-13. Score: 1

One such approach is to totally order the points of $\mathbb{R}^d$ by a space-filling curve (such as the $d$-dimensional Hilbert curve), as proposed by Bartholdi and Platzman. Given finite $G$, you simply visit its points in curve order. If you add a point to $G$, you simply insert it in the tour (two new edges).

For $n$ points in the unit cube this yields a tour of length $O(n^{1-1/d})$. In $\mathbb{R}^2$, the tour length is $O(\lg n)\cdot\mbox{OPT}$.


---

### Answer by username_2 on 2023-10-06. Score: 0

I think I understand the spirit of what you are asking, but it is difficult to answer without a clear, rigorous question. Perhaps something along the following lines:

Given a set $V$ of $n$ points in $\mathbb{R}^d$, an $(\alpha,k)$-*robust tour* is a Hamiltonian cycle $T$ through $V$ such that:

1. $\text{length}(T) \leq \alpha\cdot\text{length}(T^\*)$ where $T^\*$ is a Hamiltonian cycle through $V$ of minimum length.
2. For any $x \in \mathbb{R}^d$, there exists a Hamiltonian cycle $T'$ through $V\cup\{x\}$ such that $|T' \setminus T| \leq k+2$ and $\text{length}(T') \leq \alpha\cdot\text{length}(T^{\*\*})$ where $T^{\*\*}$ is a Hamiltonian cycle through $V\cup\{x\}$ of minimum length.

Anyway, I am unaware of anything like this being studied, but you might want to poke around searching for "robust combinatorial optimization".


---

### Answer by username_3 on 2023-11-15. Score: 0

This, technically, answers the question as posted and is a bit large for a comment, so here it is.

> 1. Compute any $c$-approximate TSP solution $P$ for $G$.
> 2. Assume WLOG by renaming that $P=(x\_1, x\_2, \ldots, x\_n)$.
> 3. Let $x\_i$ be the nearest neighbor of $x\_{n+1}$.
> 4. Return the tour $P^\*=(x\_1, x\_2, .., x\_i, x\_{n+1}, x\_{i+1}, x\_{i+2}, ..., x\_n)$ obtained by inserting $x\_{n+1}$ into $P$ after $x\_i$.

The path $P^\*$ differs from $P$ in three edges. Assuming the underlying space is metric (as Euclidean spaces are), the cost of $P^\*$ is at most the cost of $P$ plus $2 d(x\_i, x\_{n+1})$. By the choice of $P$ and $i$ this is at most $c+2$ times the cost of an optimal path for $G^\*$.

No doubt one can do better.


---

