# Stable/Robust Traveling Salesman Approximation Methods

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.

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

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}$$.

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.