# Questions tagged [traveling-salesman-problem]

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

11
questions

**1**

vote

**0**answers

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

**0**

votes

**0**answers

34 views

### Transformation of asymmetric traveling salesman problems into Chinese postman problems

I have found transformations of Chinese Postman Problems (CPPs) into Asymmetric Traveling Salesman Problems (ATSPs), but didn't find anything about transformations in the opposite direction.
Having ...

**11**

votes

**1**answer

322 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

157 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

542 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

126 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

102 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

966 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

353 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

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