All Questions
Tagged with algorithms traveling-salesman-problem
7 questions
3
votes
1
answer
161
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 ...
- 13.2k
1
vote
1
answer
115
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 ...
- 13.2k
1
vote
1
answer
347
views
Algorithm for multiple travelling salesmen problem with given starting point and end point
Given:
Set of n>0 cities is to be traversed by m>0 salespeople
Where all the salespeople:
Are positioned at the same starting city;
Finish at a same destination (which different from starting ...
- 11
11
votes
1
answer
404
views
Traveling Salesman Problem on finite group
Given a finite group $H$, define a norm on $H$ to be a function $f : H \rightarrow \mathbb{R}_{\geq 0}$ satisfying:
$f(x) = 0 \iff x = e$ is the identity;
$\forall x \in H$, we have $f(x) = f(x^{-1})$...
- 12.4k
0
votes
0
answers
59
views
A variant of travel salesman problem with charging points
Given a graph composed of a set $V$ of nodes, each representing a point to be visited by a salesman, and a set of fixed charging points. The salesman disposes a car that can travel $D$ distance before ...
- 367
0
votes
1
answer
54
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)$ ...
- 13.2k
2
votes
1
answer
139
views
Description of Linear Time Algorithm for TSP in Halin Graphs
I am looking for a description of the linear time algorithm for the TSP in Halin graphs, that was given in
"G. Cornuejols, D. Naddef, and W.R. Pulleyblank. Halin graphs and the travelling ...
- 13.2k