Questions tagged [traveling-salesman-problem]

Filter by
Sorted by
Tagged with
11
votes
1answer
321 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})$...
10
votes
1answer
700 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 ...
9
votes
4answers
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 ...
4
votes
2answers
352 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 ...
3
votes
2answers
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 ...
3
votes
1answer
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 (...
3
votes
0answers
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
1answer
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 ...
2
votes
0answers
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 ...
1
vote
0answers
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
0answers
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 ...