1
$\begingroup$

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.

$\endgroup$
0

3 Answers 3

0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.