Last call to make your voice heard! Our 2022 Developer Survey closes in less than a week. Take survey.

# Questions tagged [traveling-salesman]

The Traveling Salesman Problem and variants

224 questions
Filter by
Sorted by
Tagged with
25 views

### approximation ratio of TSP problem where the weights are bounded by an inequality

Consider a variant of the TSP problem where the cost function $c$ is not only symmetric but also satisfies $c(u, v) ≤ 2c(u, w) + c(w, v)$ for arbitrary vertices $u, v, w ∈ V$ . Give a polynomial time ...
1 vote
37 views

### Why DFS transversal without the duplicates is a valid cycle?

So I am studying apporiximation algorithms for TSP problem and there is a step that I don't get. Essentially trying to solve TSP means we are looking for a minimum cost Hamiltonian path. The well-...
57 views

1 vote
65 views

### Reduction from TSP to ATSP does not imply constant factor approximation algorithm

As I understand there is a constant factor approximation algorithm (e.g Christofides algorithm) for the symmetric TSP problem. This is however not the case for the asymmetric TSP problem (I am ...
1 vote
116 views

### $P = NP$, what am I missing?

First post here so hope I'm not missing too many guidelines. I've had this idea for a few weeks now and I can't myself see where I'm going wrong with it, hope it makes some sense to you and thanks in ...
74 views

### Clarification for binary search in solving optimal TSP when a polynomial algorithm with a budge exists

Below is Question 8.1 in Algorithms by Dasgupta et al. There's a solution to this problem that uses binary search from here. Pasting the answer for posterity. My questions are: When they say input ...
1 vote
92 views

### Why is crossing paths bad in Traveling Salesman?

I'm learning about Traveling Salesman in an online course (sorry I can't share the link it's paid only) and the first step to solving it then just state "as a heuristic we avoid crossed paths&...
61 views

### Reducing the Hamiltonian cycle to the travelling salesman problem and self loops

If this is my adjacency matrix for the hamiltonian cycle: $$\begin{pmatrix}0&1&0&1\\ 1&0&1&0\\ 0&1&0&1\\ 1&0&1&0\end{pmatrix}$$ Then a reduction ...
46 views

### Why should 3-Opt be used over 2-opt for solving TSP?

I know the working of 2-opt and 3-opt local search algorithm. But I could not find any example where solution improvement is not possible using 2-opt but 3-opt. I am looking for a proper explanation ...
50 views

### Route finding on a graph that must go through multiple edges

I have this graph It shows a graph of a map that has nodes and segments (or edges), with weights, that connect these nodes. Some of these segments have addresses on, and some of these addresses are ...
34 views

### The shortest path that visits every specified node before finally reaching the specified end node?

After asking another question(Is the last step in the Christofides' algorithm necessary), I have decided Christofide's algorithm probably doesn't solve the problem I'm facing. Is there any ...
1 vote
63 views

### Is the last step in the Christofides' algorithm necessary [closed]

I am using Christofides' algorithm to calculate the best route from one location to another given multiple nodes on a map that the route must pass through. The last step in the algorithm requires the ...
1 vote
42 views

### Cyclic tour minimizing total weight

I asked the following question on math.se but it wasn't really answered so moved it over here as I feel it's more relevant. I saw the question below on an old stack exchange question when looking to ...
1 vote
201 views

### Time complexity of the travelling salesman problem (Recursive formulation)

According to this recursion formula for dynamic programming (Held–Karp algorithm), the minimum cost can be found. I entered this code in C ++ and this was achieved (...
1 vote
205 views

### Time complexity of Tsp using DP

this is the recursion formula for problem : C(i,S) = min { d(i,j) + C(j,S-{j}) } In fact, when I tried to implement it as a code, the following code came to my ...
47 views

### How to create mathematical proof of TSP and SLAP equivalence?

In my thesis, I'm dealing with SLAP (storage location assignment problem) -- which is finding optimal distribution of products to location slots in a generic warehouse. My aim was to implement ...
50 views

### For a set of points P, connected by weighted edges (distances) I need a path through all points while minimizing the travel on any edge longer than X

For a given set of coordinates (lat/lng) I need a path which will visit each coordinate only once. The path needs to be selected to minimize the number of times the haversine distance between two ...
124 views

### TSP - Held-Karp vs Dantzig et al

I'm having trouble understanding the difference between the Held-Karp $O(n^2 2^n)$ solution and the cutting-plane method pioneered by Dantzig, Fulkerson and Johnson. Held-Karp is $O(n^2 2^n)$ which ...
55 views

### Travelling Salesman Problem: Distance between solutions

I'm designing a genetic algorithm to solve the travelling salesman problem. So far, I've gotten fairly good results. I'm now trying to improve on them by implementing some sort of diversification ...
1 vote
66 views

### What is the shortest total path between pairs of points?

I have 2n random points on a plane. Join pairs of points to make paths. Pair the points such that the summed path length is a minimum. In the picture below, we are trying to minimise the total length ...
79 views

### Bottleneck TSP with repeated nodes

I am aware that the traveling salesman problem (TSP) and the bottleneck TSP problem is NP-hard for complete directed graphs. I am also aware that regular TSP that allows a path with repeating is also ...
124 views

### Approximation concerning Asymmetric TSP, Symmetric TSP, and Metric TSP

I always considered Symmetric TSP to be inapproximable in general, and thus by extension Asymmetric TSP as well. Once you add the condition of the triangle inequality however, you obtain Metric TSP (...
66 views

### Schedule Optimization With Priority and Weighted Costs

I need an algorithm to determine the best itinerary for a series of events. Each event has a time, location, and reward. Arriving at an event in time yields the reward; too late means no reward. Each ...
59 views

### Combinatorial Problem similar in nature to a special version of max weighted matching problem

I have a problem and want to know if there is any combinatorial optimization that is similar in nature to this problem or how to solve this special version of the max weight matching problem. I have a ...
1 vote
63 views

### TSP 200-approximation, given $c(x,z)\le c(x,y) + 100\cdot c(y,z)$ for all nodes $x,y,z$

Input: complete, undirected graph $G=(V,E)$ and cost function $c$ Assume for all nodes $x,y,z \in V$: $c(x,z)\le c(x,y) + 100\cdot c(y,z)$ Find a 200-approximation polynomial time algorithm for the ...
Is the travelling salesman problem (TSP) $FNP$-complete or is it $FP^{NP}$-complete?