# Questions tagged [tsp]

The travelling salesman problem (TSP) is an NP-hard problem in combinatorial optimization studied in operations research and theoretical computer science. Given a list of cities and their pairwise distances, the task is to find a shortest possible tour that visits each city exactly once.

54 questions
Filter by
Sorted by
Tagged with
14k views

### Approximation algorithms for Metric TSP

It is known that metric TSP can be approximated within $1.5$ and cannot be approximated better than $123\over 122$ in polynomial time. Is anything known about finding approximation solutions in ...
• 2,247
2k views

### DNA-algorithms and NP-completeness

What is the relationship between DNA-algorithms and the complexity classes defined using Turing machines? What do the complexity measures like time and space correspond to in DNA-algorithms? Can they ...
• 283
957 views

### Approximate 1d TSP with linear comparisons?

The one-dimensional traveling salesperson path problem is, obviously, the same thing as sorting, and so can be solved exactly by comparisons in $O(n\log n)$ time, but it is formulated in such a way ...
• 51.1k
1k views

### Solving Superstring Exactly

What is known about exact complexity of the shortest superstring problem? Can it be solved faster than $O^*(2^n)$? Are there known algorithms that solve shortest superstring without reducing to TSP? ...
• 2,247
1k views

This question was previously posted to Computer Science Stack Exchange here. Imagine you're a very successful travelling salesman with clients all over the country. To speed up shipping, you've ...
• 253
1k views

### Classes of graphs with easy Hamiltonian cycle but NP-hard TSP

The Hamiltonian Cycle Problem (HC) consists in finding a cycle that goes through all vertices in a given undirected graph. The Travelling Salesman Problem (TSP) consists in finding a cycle that goes ...
• 955
880 views

### Euclidean TSP in NP and square root complexity

In this lecture notes by Ola Svensson: http://theory.epfl.ch/osven/courses/Approx13/Notes/lecture4-5.pdf, it is said that we don't know if Euclidean TSP is in NP: The reason being that we do not ...
• 373
395 views

### Error in paper "Some NP-complete geometric problems"?

The paper in question: M.R. Garey, R.L. Graham and D.S. Johnson. Some NP-complete geometric problems . This paper proofs the NP-completeness of some well-known problems, such as the Steiner Tree ...
• 275
840 views

### Any SAT/SMT formulations of the VRP/VRPTW (TSP, Job-Shop-Scheduling)?

i wonder if they are any approaches formulating a Vehicle-Routing-Problem with Time-Windows (VRPTW) (as a decision problem) as a SAT/SMT instance? (alternative: TSP) For example: "Is there a valid ...
• 203
620 views

### Special cases of Graphic TSP

In Graphic TSP, you are given an unweighted undirected graph $G$ and the goal is to find a shortest tour in $G$ that visits every vertex at least once. Note that this is NOT same as finding a ...
• 10.6k
1k views

### Generating interesting combinatorial optimization problems

I'm teaching a course on meta-heuristics and need to generate interesting instances of classic combinatorial problems for the term project. Let's focus on TSP. We are tackling graphs of dimension $200$...
7k views

### Time complexity of Held-Karp algorithm for TSP

When I looked through "A Dynamic Programming Approach to Sequencing Problems" by Michael Held and Richard M. Karp1, I came up with the following question: why the complexity of their ...
• 4,215
280 views

• 71
689 views

### Travelling Salesman and Planar Travel - Generalized TSP

Our beloved Travelling Salesman just bought the Manual of the Planes and wants to make some use of it. He is not a great adventurer though, so he will restrain his travels in the Parallel and ...
• 207
203 views

### Given a set of distances (no info regarding what points the distances correspond to) from a complete graph, is the realization of the graph unique?

There are $n$ points in $R^2$ (i.e. the 2D real space). We can think of them as a complete graph where edge weights correspond to the distance between points. Let $D$ be the distance matrix between ...
• 63
1k views

### Euclidean TSP algorithms

Are there any known exact algorithms for Euclidean TSP that take advantage of the inherent structure of the problem? Do any of these algorithms have better asymptotics than $O(2^n n^2)$ of a DP ...
• 161
165 views

### N shortest tours in a graph

I'm searching for papers dealing with the problem of finding not just the shortest tour in the graph (TSP) but finding N shortest tours. Somewhat surprisingly, I didn't find any mention of it, ...
754 views

### Shortest cycle with a specific number of vertices

Given an undirected graph with n nodes, I need to find the shortest cycle of involving exactly n/2 vertices (i.e. keeping the distance traveled by the cycle to a minimum). Some nodes cannot directly ...
• 163
2k views

### Approximation for metric TSP: Worst case using nearest neighbor heuristic?

I'm looking at different heuristics that approximate solutions for a metric Traveling Salesman Problem. I was wondering if there is a worst case ratio of tours calculated by the nearest neighbor ...
• 153
15k views

### what is the real difference between traveling salesman problem (TSP) and vehicle routing problem (VRP)?

Both problems are well-known NP-hard problems with great similarities. In fact, I do not see the real difference between these two problems. It seems relatively easy to model TSP in the form of VRP ...
• 467
2k views

### Good algorithms to solve ATSP

What are some good neighborhood-based local search algorithms or strategies to solve the Asymmetric TSP ? I see many 2-OPT and K-opt based algorithms (e.g. Lin-Kernighan implementations), but I think ...
• 171
247 views

### What is known about (upper bounds on) the LP gap of the (symmetric) Travelling salesman in special instances?

What is known about the LP gap of (the natural Held-Karp relaxation of) the (symmetric) Travelling salesman in special instances? I'm only aware of one special case where the extreme points are all ...
• 228
293 views

### A Travelling Salesman variant where the next distance depends on distance travelled so far

The travelling salesman problem can be seen as a problem of selecting a permutation on $\{1,\ldots,n\}$ of minimun length, where the length of a permutation $\sigma$ is determined by pairwise ...
• 2,262
1k views

### Heuristics for tsp without triangle inequality

Every heuristic for the traveling salesman problem that I know of (Nearest-Neighbour, Christofides, Held-Karp, ...) assumes that the triangle inequality holds. Are there heuristics to solve the tsp ...
• 227
637 views

### Parameters of energy function for TSP

[This question was initially asked here. It went unanswered so I thought I should ask it in a different community.] I am reading this paper by Hopfield et al. On page six, the authors defined the ...
• 651
989 views

### Why is Metric TSP's best possible achieved approximation ratio believed to be 4/3?

Is it just that integrality gaps (LP/IP) for specific instances do not give more than 4/3? Thanks in priori.
• 573
629 views

### TSP with multiple visits

Can you please suggest possible approaches for the following problem: Find a path through graph vertices so that the distance (sum of edges weights) between two vertex $i$ occurrences would be no ...
67 views

### Complexity of comparing polygon perimeters

The problem of comparing the lengths of two paths of line segments connecting points in $\mathbb{Q}^2$ is not known to be in $\text{P}$, nor even in $\text{NP}$. Does requiring that the paths begin ...
• 548
1k views

### Christofides algorithm for directed graph

Is it possible to implement the Christofides algorithm for an directed Graph? Suppose you have an undirected Graph, in which every vertex has an edges in both ways to every other in the graph (not to ...
• 31
243 views

### Ordered routing problem which is NP-hard

All the np-hard routing problems I know are of the form, minimize some quantity while visiting the verticies in an unordered way. Are there problems which are still np-hard, if one has to visit the ...
• 31
392 views

### Travelling Salesman Problem where a subset of the nodes must be visited in a particular order

I’m curious whether there is any work on the variant of the Travelling Salesman Problem where a subset of the nodes must be visited in a particular order. I haven’t found anything with searches or in ...
913 views

### Ant colony optimization for traveling salesman problem with changing graph-nodes/vertices

Are there any publications focusing on solving TSP with ant colony optimization that consider small changes in the graph's nodes or vertices? So what I have is: a traveling salesman problem (TSP) ...
• 123
207 views

### Question on the Prize-Collecting TSP's ratio related to inapprox. of general TSP

The Prize-Collecting TSP (PCTSP) is defined as the ordinary TSP with the difference that penalties are added to nodes; so we may avoid visiting a node paying its penalty, which is added to the overall ...
• 573
398 views

### ATSP with direction restrictions

I'm trying to find any material on this problem. It extends the Asymmetric Travelling Salesman Problem (ATSP) in that it requires for some destinations that they are approached in the specified ...
• 211
50 views

### Ordering tours in a Euclidean TSP according to (strictly) increasing length

Let $H$ be the set of all Hamiltonian cycles on the complete graph $K_n$ associated with a set of $n \geq 4$ points $P$ in the plane where edge weights are defined using the Euclidean distance between ...
• 21
438 views

### Arora's PTAS for Euclidean TSP details

I'm currently doing an internship, in which studying TSP and its algorithms are involved. I'm doing fine with understanding the 2 and 1.5-approximation algorithms for the Metric TSP, but when I come ...
• 275
1 vote
243 views

### Simple spatial ordering or TSP algorithms?

I'm not sure if this is the right place to ask, but I suppose you'll tell me. I'm writing a program that produces a series of points on a map, and I need to put the points in some linear order so ...
• 111
1 vote
629 views

### Generate TSP instances with known optimal

Is there a known (polynomial in number of nodes) algorithm to generate TSP instances with known optimal value? The idea is to be able to generating arbitrary large instances with known optimal value,...
• 199
1 vote
223 views

### Cheapest Insertion is $2$-approximation for TSP

Consider the Cheapest Insertion Algorithm on a complete graph with $n$ vertices, where each edge $uv$ has a weight $w(uv)$, and the weights satisfy the triangle inequality $w(xz)\leq w(xy)+w(yz)$ for ...
1 vote
48 views

### TSP variant in which edge costs depend on the already visited vertices

Does a TSP variant exist in which edge costs depend on the vertices already visited? For instance, if you already visited vertices A, B, and then C, in that order, then now the cost to traverse CD = 5,...
• 11
155 views

### TSP heuristics for limited distance information

this is my first question on Theoretical CS. :) I've posted a similiar question on Mathoverflow and a friendly user advised me to post my question on this site. Problem: I'm looking for TSP ...
• 103
323 views

### PTAS (polynomial time approximatin scheme) for euclidean TSP/Minimum-Cost k-Connected subgraph problem

Problem 1 I have read "On Approximation of the Minimum-Cost k-Connected Spanning Subgraph Problem" (by A. Czumaj, A. Lingas), and even in the abstract are 2 statements "We present a ...
• 201
59 views

### Reduction from Traveling Salesman

Consider the decision problem: "Given a complete weighted graph $G=(V,E)$, an integer $k\in\mathbb N$ and two nodes $s,t\in V$ decide if $G$ has a path of at least weight $k$" I had to ...
• 11
91 views

### Is the traveling salesman problem still NP-hard if all edges need to be covered as well?

If we formulate the travelling salesman problem with an added edge-covering constraint as follows, is it still NP-hard? Given a graph G with non-negative edge weights, is there a circular walk in G ...
88 views

### Approximation Algorithm for TSP-like problem

Suppose we are given a graph with distances for each of the edges and merit for each of the nodes. What are the best (approximation) algorithms for computing the the most meritorious simple path with ...
• 441
I would like to ask whether there exists a better approximation result on a special case of the ATSP metric instances: when cost(a,b)=cost(b,a) for $O(log(|E|)$ edges, or something close/related to ...