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.

Filter by
Sorted by
Tagged with
46 votes
4 answers
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 ...
Alex Golovnev's user avatar
21 votes
4 answers
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 ...
Aadita Mehra's user avatar
21 votes
1 answer
948 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 ...
David Eppstein's user avatar
18 votes
3 answers
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? ...
Alex Golovnev's user avatar
15 votes
2 answers
1k views

What is known about this TSP variant?

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 ...
David Zhang's user avatar
14 votes
3 answers
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 ...
Standa Zivny's user avatar
12 votes
2 answers
869 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 ...
JS_'s user avatar
  • 363
11 votes
0 answers
393 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 ...
J. Schmidt's user avatar
10 votes
1 answer
832 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 ...
sascha's user avatar
  • 203
9 votes
3 answers
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 ...
Shiva Kintali's user avatar
9 votes
2 answers
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$...
Alejandro Piad's user avatar
9 votes
2 answers
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 ...
Oleksandr Bondarenko's user avatar
9 votes
0 answers
280 views

Advances towards proving the Held-Karp conjecture for TSP

I've only began my research into the Held-Karp conjecture and I was wondering about recent progress in proving the conjecture. The Held-Karp relaxation is conjectured to have an integrality gap of $\...
Quanquan Liu's user avatar
7 votes
2 answers
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 ...
Eli's user avatar
  • 343
6 votes
3 answers
2k views

A simple approximation algorithm for the TSP

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 ...
Sacha's user avatar
  • 338
6 votes
1 answer
4k views

Guidelines to reduce general TSP to Triangle TSP

I am looking for the method / correct way to approach to reduce the traveling salesman problem to an instance of traveling salesman problem which satisfies the triangle inequality, ie: $D(a, b) \leq ...
Dave's user avatar
  • 71
6 votes
2 answers
682 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 ...
aronisstav's user avatar
6 votes
2 answers
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 ...
RachM's user avatar
  • 63
6 votes
0 answers
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 ...
Paul Miller's user avatar
6 votes
0 answers
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, ...
smartyfish's user avatar
5 votes
1 answer
750 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 ...
rptynan's user avatar
  • 163
5 votes
1 answer
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 ...
Johannes's user avatar
  • 153
5 votes
3 answers
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 ...
sma's user avatar
  • 467
5 votes
2 answers
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 ...
yafrani's user avatar
  • 171
5 votes
1 answer
243 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 ...
Hao S's user avatar
  • 228
4 votes
3 answers
287 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 ...
Erel Segal-Halevi's user avatar
4 votes
1 answer
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 ...
Aerus's user avatar
  • 227
4 votes
1 answer
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 ...
Omar Shehab's user avatar
4 votes
2 answers
985 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.
N27's user avatar
  • 573
4 votes
1 answer
628 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 ...
Goldwin_es's user avatar
4 votes
0 answers
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 ...
Dan Brumleve's user avatar
3 votes
0 answers
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 ...
paul's user avatar
  • 31
3 votes
0 answers
238 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 ...
alex's user avatar
  • 31
2 votes
1 answer
387 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 ...
Robin Houston's user avatar
2 votes
2 answers
912 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) ...
Fabian Schuh's user avatar
2 votes
1 answer
205 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 ...
N27's user avatar
  • 573
2 votes
1 answer
396 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 ...
Max's user avatar
  • 211
2 votes
0 answers
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 ...
axplusbu's user avatar
2 votes
0 answers
436 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 ...
J. Schmidt's user avatar
1 vote
3 answers
240 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 ...
Qwertie's user avatar
  • 111
1 vote
1 answer
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,...
AndresQ's user avatar
  • 199
1 vote
0 answers
216 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 ...
Ioana Roman's user avatar
1 vote
0 answers
47 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,...
B. Dylan's user avatar
0 votes
1 answer
154 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 ...
aGer's user avatar
  • 103
0 votes
1 answer
321 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 ...
Ramzi Kahil's user avatar
0 votes
0 answers
57 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 ...
Green's user avatar
  • 11
0 votes
0 answers
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 ...
Sebastian Schmidt's user avatar
0 votes
0 answers
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 ...
ruadath's user avatar
  • 441
0 votes
0 answers
68 views

Asymmetric metric TSP when many edges have equal costs in both directions

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 ...
NicosM's user avatar
  • 47
0 votes
0 answers
436 views

Worst case of heuristics for symmetric TSP

I have implemented the nearest neighbor heuristic for solving symmetric TSP problems. I was wondering if there is any relation between the solution found by the heuristic and the optimal solution? ...
user19553's user avatar