# 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
72 views

### Hardness of the Metric TSP for the Maximum Metric

I know that it is not too difficult to construct a metric to show that the metric TSP is NP-hard. The typical example is (1,2)-TSP. I also know that Papadimitriou has shown that Euclidean TSP is NP-...
• 63
301 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,294
201 views

### Bottom up TSP solution?

I'm not sure if this is something new or if I'm just not getting previous efforts. TSP can be thought of as a list of weighted links and nodes. If one takes the Nearest Neighbor (NN) of every node and ...
1 vote
230 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 ...
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
93 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 ...
1 vote
49 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
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
396 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
68 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
439 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
901 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
398 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 ...
196 views

### Dance Partner Problem NP-completeness [closed]

I really can't think of a concise way to phrase this problem, which makes it hard to search for, so forgive me if this is a duplicate question. I've come across a problem and I would like to know if ...
• 101
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
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
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
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 ...
• 461
282 views

• 71
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
964 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
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 ...
622 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
245 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
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
884 views

### Algorithm to maximize profit: ways to solve/approach? (Advanced NP-Complete)

This one's hard, so all help really appreciated! I know it is NP-Complete and thus cannot be solved in polynomial time, but looking for help in analysis, i.e. what type of NP-Complete problem it ...
• 129
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
695 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
213 views

### Is there a series of algorithms for approximating TSP polynomially?

I've began studying some CS recently, and I've faced the TSP. The decision problem version of the TSP is NP-complete, right? I've noticed (and elaborated myself) that there exists several polynomial ...
• 101
1 vote
245 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
208 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
994 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
317 views

### Is there a local variant of TSP?

I'm a traveling salesman and I have n days to sell, I can start anywhere, I can sell once per city. I want to know where to start and what route to take. It's likely NP-hard, I was just wondering if ...
• 343
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
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
Consider the following extremely simple approximation algorithm for the TSP. Input: A complete weighted graph $G=(V,E).$ Take any three vertices $a,b,c\in V$ and let $H:=(a,b,c,a).$ While there ...