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
2
votes
1
answer
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
4
votes
3
answers
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
-1
votes
2
answers
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
0
answers
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 ...
- 11
5
votes
1
answer
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
0
votes
0
answers
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
0
answers
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
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 ...
- 21
11
votes
0
answers
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
4
votes
0
answers
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
2
votes
0
answers
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
13
votes
2
answers
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
2
votes
1
answer
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 ...
- 761
-5
votes
1
answer
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
0
votes
1
answer
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
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 ...
- 253
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 ...
- 171
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 ...
- 461
9
votes
0
answers
282
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 $\...
- 323
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 ...
- 31
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 ...
- 47
0
votes
0
answers
437
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?
...
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 ...
- 227
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 ...
- 161
6
votes
2
answers
204
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
4
votes
1
answer
639
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 ...
- 661
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 ...
- 153
0
votes
1
answer
324
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
1
vote
1
answer
634
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
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, ...
- 61
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$...
- 193
5
votes
1
answer
762
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
6
votes
1
answer
5k
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 ...
- 71
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 ...
- 467
21
votes
1
answer
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
4
votes
1
answer
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 ...
- 41
9
votes
3
answers
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
3
votes
0
answers
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
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?
...
- 2,247
0
votes
0
answers
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
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 ...
- 2,247
6
votes
2
answers
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
0
votes
0
answers
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
3
answers
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
2
votes
1
answer
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
4
votes
2
answers
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
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 ...
- 343
2
votes
1
answer
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
2
votes
2
answers
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
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 ...
- 338