# Questions tagged [traveling-salesman-problem]

The traveling-salesman-problem tag has no usage guidance.

25
questions

**0**

votes

**0**answers

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

**0**

votes

**0**answers

15 views

### Tour expansion with min-cost flow

Question:
has the problem of formulating optimal tour-expansion for Symmetric TSP's already been mentioned as a means for faster tour-expansion in the sense of potentially intergrating more than one ...

**0**

votes

**0**answers

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

**0**

votes

**1**answer

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

**0**

votes

**0**answers

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

**-1**

votes

**1**answer

177 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:
several questions arise from that ...

**0**

votes

**0**answers

19 views

### Probability that edge exchange yields a tour

let $H$ be a Hamilton cycle in a complete topological symmetric graph $G$ of finite size.
Question:
what is the probability that a vertex-disjoint cycle cover $C_k$ that is generated from $H$ by ...

**1**

vote

**1**answer

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

**0**

votes

**1**answer

35 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)$ ...

**0**

votes

**0**answers

35 views

### Examples of recursive TSP heuristics

Question:
What are examples of heuristics for the Traveling Salesman Problem, that are recursive in the sense that they can efficiently calculate the shortest Hamilton cycle in a graph if the optimal ...

**3**

votes

**0**answers

67 views

### Additional symmetries of the Traveling Salesman Polytope

Given the complete graph $K_n=(V,E)$, the Traveling Salesman Polytope is a convex polytope in $\Bbb R^E$ obtained as the convex hull of the indicator vectors of (edge-sets of) Hamiltonian cycles in $...

**0**

votes

**0**answers

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

**1**

vote

**1**answer

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

**0**

votes

**0**answers

18 views

### Is there one 1.5 approximate algorithm to solve edge-fixed TSP and TSP path?

Since we have a 1.5-approximate problem on TSP (Travelling Salesman Problem) and TSP path (under conditions of fixing the start point of the path or fixing one point or fixing two points of the path) ...

**2**

votes

**0**answers

63 views

### Trying to understand "moats"

According to the TSP Gallery moats provide lower bounds for the optimal solution of TSP instances.
On the webpage they are depicted as blue rings around red disks, whose radii represent maximal vertex ...

**1**

vote

**0**answers

130 views

### Mathematical problems reducing to the traveling salesman problem

The superpermutation problem is: what is the shortest word that contains every permutation of $k$ letters as a substring. This can phrased as a Travelling Salesman Problem, where the nodes of your ...

**11**

votes

**1**answer

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

**3**

votes

**1**answer

196 views

### What is known about this TSP variant?

Euclidian (planar) TSP asks for a tour with the minimum total length. The problem is known to be NP-hard. I am interested in the variant of finding a closed tour with the minimum enclosed area (...

**9**

votes

**4**answers

562 views

### What would $\mathcal{P} \neq \mathcal{NP}$ tell us about some non-constructive proofs?

Let me sum up my - hopefully correct - understanding of the travelling salesman problem and complexity classes. It's about decision problems:
"[...] a decision problem is a problem that can be ...

**2**

votes

**1**answer

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

**3**

votes

**0**answers

113 views

### Hamiltonian cycle polytope for the hypercube graph

Let $Q_n$ denote the $n$ dimensional hypercube graph (i.e., graph formed from the vertices and edges of an n-dimensional hypercube). Denote the set of edges and vertices of $Q_n$ by $E_n$ and $V_n$ ...

**2**

votes

**0**answers

115 views

### Corporate salesman problem

A salesman is employed by a large corporation. He has a $n$ cities to visit, connected by roads, forming a graph. But as travel takes a lot of time, he has to pick hotels between visits. He cannot ...

**3**

votes

**2**answers

1k views

### Is there a lower bound for the computational complexity of the traveling salesman problem?

A (non-mathematician) acquaintance of mine recently proposed to me a polynomial-time algorithm for solving the traveling salesman problem. While I was able to point out a flaw in his approach, it did ...

**4**

votes

**2**answers

369 views

### What Kind of Graph is This?

I am currently developing TSP heuristics that aim at symmetrically reducing the original, complete and undirected graph.
The overarching rationale is that the reduction is done via a sequence of ...

**11**

votes

**1**answer

743 views

### Generalized Euclidean TSP

Suppose I have n sets $X_1,\dots,X_n$ consisting of $k$ points each, where all $nk$ points are i.i.d. uniform random samples in the unit square $[0,1]\times[0,1]$. Consider the shortest path that ...