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.
0
votes
1answer
57 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 polynomial time ...
0
votes
0answers
120 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 ...
6
votes
0answers
90 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, ...
5
votes
0answers
94 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 ...
4
votes
1answer
284 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 ...
1
vote
1answer
268 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 ...
2
votes
0answers
480 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 TSR in the form of VRP ...
21
votes
1answer
338 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 ...
2
votes
0answers
156 views
TSP with multiple visits
Can you please suggest possible approaches for the following problem: find a path through graph verticies so that the distance (sum of edges weights) between two vertex i occurrences would be no more ...
9
votes
3answers
347 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 ...
3
votes
0answers
171 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 ...
15
votes
3answers
682 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?
...
0
votes
0answers
229 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 ...
30
votes
4answers
3k 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 ...
6
votes
2answers
329 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 ...
0
votes
0answers
158 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 ...
1
vote
3answers
152 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 ...
2
votes
1answer
144 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 ...
4
votes
2answers
446 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.
6
votes
2answers
249 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 ...
2
votes
1answer
362 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 ...
2
votes
1answer
570 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)
...
6
votes
3answers
1k 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 ...
11
votes
3answers
560 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 ...
8
votes
1answer
3k 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. Karp, I came up with the following question:
why the complexity of their algorithm for TSP ...
8
votes
1answer
357 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 ...
18
votes
4answers
657 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 ...
