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.

19 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
11 votes
0 answers
392 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
9 votes
0 answers
278 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
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
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
237 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
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
433 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
0 answers
213 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
2 answers
151 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 ...
Maub Nesor's user avatar
0 votes
0 answers
55 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
89 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
435 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
0 votes
0 answers
871 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 ...
Jason's user avatar
  • 129
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 ...
Real's user avatar
  • 101