1
$\begingroup$

Assume I have a euclidean TSP solver that is optimal, but it can only solve inputs with exactly $N$ vertices. Let's call it the N-solver.

Now, I have an input with $K$ vertices in the 2D plane, where $K < N$. Can I convert this $K$ sized input to an $N$ sized input where I can feed it into my N-solver and obtain an optimal answer, and then try to convert it back to an optimal solution for the original $K$ vertices?

I assume that you are not allowed to have multiple vertices at the same coordinate.

Has this problem been discussed, investigated, or solved anywhere? Even some approach that guarantees some gap compared to the optimal answer would be good. Any thoughts?

$\endgroup$
4
  • $\begingroup$ Add a set $FO$ of $N - K$ vertices far out? None should be included in an optimal answer. $\endgroup$
    – greybeard
    Jun 19 at 8:07
  • $\begingroup$ @greybeard That was my initial thought. However, I need mathematical guarantee. Therefore, it begs the question: how far? Let's say we add those $N-K$ vertices in an infinite far distance. Since the answer is a tour, it passes through every vertex. Those far away vertices are also included (in other words, we have at least 2 transitions between the original $K$ nodes and those $N-K$ far away nodes). I couldn't guarantee any optimality gap for the path that is generated for the original $K$ vertices in this construction (since we need to add another edge to make a Hamiltonian cycle for them). $\endgroup$ Jun 19 at 8:45
  • $\begingroup$ (Dang. Somehow I diverted from cycle to shortest path.) $\endgroup$
    – greybeard
    Jun 19 at 8:58

1 Answer 1

0
$\begingroup$

If you need a mathematical guarantee, you should run $k-1$ times the $N$-solver algorithm. In other words, repeat the following approach for each vertex $v_i\ \ i=2,...,k$ and take the best solution.

Introduce $N-K$ new vertices $V_j\ \ j=k+1,...,N$ on the line segment between two vertices $v_1$ and $v_i$; e.g. With distance $d_{1j}=(j-k)\frac{d_{1i}}{N-K+1}$ and $d_{ij}=d_{1i}-d_{1j}$. Then, if $x_{1i}=1$ in the optimal solution on $k$ vertices then on N vertices we have $x_{1,k+1}=x_{k+1,K+2}=...=x_{N-1,N}=x_{Ni}=1$ with a same optimal value .

But, if you want to execute the idea of @greybeard, find $d_{a,b}=max\{d_{ij}\}$ and add $N-k-1$ far away new vertices $V_j\ \ j=k+1,...,N-1$ on the left side of the line $v_a-v_b$; e.g. With distance $d_{aj}=(d_{a,b})^{10}+j$ and $d_{bj}=d_{aj}+d_{ab}$. Moreover, add a new vertex $v_N$ close to the vertex $v_a$ as much as it is possible.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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