# Questions tagged [traveling-salesman-problem]

The tag has no usage guidance.

39 questions
Filter by
Sorted by
Tagged with
1 vote
52 views

### A generalized/set hamiltonian cycle problem on directed graphs

So this problem originally stems from the asymmetric generalized/set TSP problem, where I am interested in asking the question which or how many edges I can delete while maintaining feasability. The ...
• 111
26 views

### Monotony of enforced subtour merging

Is it true that for a symmetric TSP instance in the sequence of edges generated by successively: calculating the optimal 2-factor adding cardinality constraints on the edgesets of the 2-factor's ...
• 12.7k
1 vote
42 views

### Complexity of the TSP for hypercube graphs

Question: what is known about the complexity of finding the Hamilton cycle of minimum weight in graphs that resemble hypercubes with weighted edges?
• 12.7k
113 views

### Constructing optimal Hamilton cycles from optimal Hamilton paths

Question: can the shortest Hamilton cycle in a complete symmetric graph with weighted edges be constructed from the shortest Hamilton path in the same graph by connecting its ends and then exchanging ...
• 12.7k
46 views

### Approximation factor for TSP Algorithm

The literature that I have reviewed shows examples of calculations of known approximation algorithms such as the Christofides' algorithm for the TSP. However, I have not been able to find information ...
91 views

### Reformulate Traveling Salesman Problem in areas traversed problem

I was wondering whether one has ever considered to reformulate TSP in terms of the areas traversed in either direction. Thus take three initial points of the solution they span a triangle with a ...
13 views

### Identifying optimization-potential in weighted Hamilton cycles

From the (possibly incorrect) assumption that inoptimality of weighted Hamilton cycles, that resemble a heuristic solution to a TSP problem, can be identified by calculating the MST (minimum spanning ...
• 12.7k
67 views

### Adapting Held–Karp algorithm to visit groups of vertices

The Held–Karp algorithm has exponential time complexity $\Theta\left(2^n n^2\right)$, which is better than brute forcing the TSP which requires $\Theta(n !)$. I'm interesting in amending the Held–Karp ...
• 101
1 vote
55 views

### Knotted Traveling Salesperson route

Let us consider fixed points in space, if we apply the well-known Traveling Salesperson Problem algorithm, we get the shortest route. It can give a nontrivial knot in the three-space. The question is ...
• 71
153 views

### Fastest algorithm for calculating optimal tours in weighted $K_5$

Weighted $K_5$ have the unique property that their edge set can be interpreted as the disjoint union of their shortest and their longest Hamilton cycle. That makes $K_5$ attractive for designing new ...
• 12.7k
1 vote
90 views

### Traveling Salesman: Optimization over cities, not distance

In the classical traveling salesman problem, we are given a graph of cities with distances between each city and are asked to find the shortest path that traverses all of the cities. Meaning that the ...
144 views

### Greedy euclidean tour expansion - a case of unexpected hanging?

In the euclidean plane an common heuristic for the TSP is to start with the convex hull of the point set and then successively integrate as the next point and insertion position the combination that ...
• 12.7k
115 views

### Traveling salesperson problem algorithm [closed]

I was wondering something, let's say in a symmetric distance matrix of a sample of TSP, there was a sure algorithm that could remove between 30% to 80% of the values (distances) that wouldn't ...
149 views

### References for geometric properties of optimal Euclidean traveling salesman tour

Consider a finite set of points $V \subseteq \mathbb{R}^2$ as a TSP-instance under the standard $\| \cdot \|_2$ norm. (TSP stands for traveling salesman tour.) We know that every optimal TSP tour $T$ ...
1 vote
104 views

### Characterization of greedy TSPs?

Define a greedy tour of a set $S=\{p_1,\ldots,p_n\}$ of $n$ points in $\mathbb{R}^2$ as produced by selecting the $i$-th point $p_i$ to start, and then connecting to the nearest neighbor $p_j$ to $p_i$...
• 149k
26 views

### Are there any examples of "autonomous" TSP heuristics

By "autonomous" TSP heuristic I mean algorithms whose reported edge-set for a short Hamilton cycle is invariant under the addition of vertex weights; the terminology is borrowed from ...
• 12.7k
1 vote
32 views

• 12.7k
70 views

### TSP on a unitary circle

I am interested in knowing which is the expected length of a random path in a circle. That is, if there are $n$ random points located in the unitary circle $\{(x,y): x^2+y^2\leq 1\}$, what is the ...
55 views

### Degree-constraints for the existence of vertex-disjoint directed cycle covers in digraphs

Given a digraph $G(E,V): (u,v)\in E\implies(v,u)\notin E$, what is known about lower bounds on the indegree and outdegree of the vertices that guarantee the existence of a vertex-disjoint directed ...
• 12.7k
1 vote
162 views

### Could you provide some TSP examples from real world to test a new algorithm?

It's well known that to find a hamilton cycle is NPC, while TSP is NPH. But it seems that for majority of graphs (density of edge > 0.1, order > 100) there is a fast algorithm to find different ...
• 165
67 views

### Travelling salesman problem with variable weights

Take a fully connected graph with $v$ vertices. We assign weights to edges using an arbitrary function $f_{ij}(x)$ for pairs of vertices $0 < i, j \le v$, then starting at $c_{0}=0$, traverse the ...
• 79
240 views

### Helsgaun's $k$-Opt moves

In his 2009 paper General k-opt submoves for the Lin–Kernighan TSP heuristic, Helsgaun defines the local tour improvements on which the LKH heuristics are based as: with a cycle defined here: which ...
• 12.7k
1 vote
103 views

### $\mathrm{LP}$ formulation for $\mathrm{k}$-$\operatorname{opt}$ moves

$\mathrm{k}$-$\operatorname{opt}$ moves are an idea to improve non-optimal Hamilton cycles in weighted symmetric graphs by exchanging $\mathrm{k}$ tour-edges with $\mathrm{k}$ edges that do not belong ...
• 12.7k
52 views

### Relation of 1-trees to optimal tours

Question: given a complete symmetric graph $G(V,E)$ with $n$ vertices and edges $e_{ij}$ having weight $\omega_{ij}$, does there always exists a vector of vertex potentials $(\pi_1,\,\dots,\,\pi_n)$ ...
• 12.7k