Stable/Robust Traveling Salesman Approximation Methods

Question

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.

Answer 1

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 2

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 3

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.