# Questions tagged [traveling-salesman]

The Traveling Salesman Problem and variants

245 questions
Filter by
Sorted by
Tagged with
34 views

### Variation of Travelling Salesman Problem without matrix

Suppose we define a variation of the decision TSP in which instead of using a matrix to set the distances between cities ($n+1$), we assume every path ($n!$) uses completely different weights set at ...
45 views

### NP-Hard version of TSP if P=NP

If P=NP (polynomial time algorithm for determining whether there exists a route smaller than L) would the NP-Hard version of TSP (finding the minimum distance route) still be NP-Hard? We would only ...
1 vote
14 views

### complexity theory: polynomial hierarchy for function problems / TSP with output

I'm searching for equivalent problem classes from the polynomial hierarchy to function problems. I have this problem similar to traveling salesperson, which imo lies in the second order of polynomial ...
• 111
86 views

### How does the half-integer spanning-tree problem contain the TSP?

I am trying the understand the following statement from the book of Grotschel, Lovasz and Schrijver: Here, $\delta(W)$ is the set of edges incident to a set of vertices $W$. They define an ...
• 5,994
35 views

### How to get the TSP using DP algorithm can use 40 vertices?

Im currently doing my homework that solving TSP using DP algorithm or branch and bound algorithm or backtracking algorithm only to solve up to 40 vertices and I can solve up to 30 vertices when I try ...
• 1
52 views

### Understanding the "Structure Theorem" for the Euclidean Traveling Salesman PTAS

I am trying to understand the "Structure Theorem" in Arora's TSP slides. In particular, I do not understand the image on slide 13-3 (page 68 of the PDF). The high level idea is to show that (...
• 232
36 views

### Calculating approximation factor of a TSP algorithm

The literature that I have reviewed shows examples of calculations of known approximation algorithms such as the Christofides' algorithm for the TSP. However, I have not been able to find information ...
92 views

### Finding the optimal trading route with output amount based on previous trades

I am trying to solve the following problem: Suppose there are traders who can exchange one good for another. Each trader $i$ defines two functions $y = f_{i1}(x)$ and $x = f_{i2}(y)$, with which we ...
45 views

### Doubt on nearest-neighbour approach to solve TSP

I am a math undergrad and we have algorithms as one of our courses. We came across TSP and algos to solve them. I thought of an algorithm and apparently its already known as the Nearest Neighbour ...
1 vote
144 views

### Chistofides' algorithm for the traveling salesman problem with relaxed triangle inequality

It is known that Christofides’ algorithm returns a 3/2-approximation for the traveling salesman problem given a complete graph $G$ such that distances obey the triangle inequality. Suppose that we ...
62 views

### Is One Way TSP NP-Complete?

I know that finding the optimal solution to One Way TSP (TSP but the salesman does not have to return to his original city) is NP-Hard, but is it NP-Complete? I ask this because I recently found a ...
• 103
66 views

### Is this a Traveling salesman problem? If so, how to solve it?

Given a group of cities and a starting city, we have to find a path that covers all the cities. The path doesn't need to end at the starting city. Is this a TSP problem? What is the solution for it? ...
• 115
91 views

### Transforming a Travelling Salesman Problem to a Maximum Clique Problem

Say you have a directed graph consisting of n nodes and containing edge weights. A starting node is also given. You want to begin your route at that node and visit each other node in the graph exactly ...
68 views

### Is the traveling salesman on a map NP-hard?

It is known that the general traveling salesman problem is NP-hard. Even when the distances follow the triangle inequality. But let's take the problem very literally. There are actual cities (points) ...
• 377
82 views

### constructing non-trivial graph with known shortest Hamiltonian path

I'm interested in testing some Traveling Salesperson (TSP) greedy approximation algorithms for finding the shortest Hamiltonian path for very large graphs. Assume I can construct whatever graph I ...
• 121
104 views

### How to prove that this problem is NP Complete

I have a problem set about NP Completeness proofs and I'm struggling to approach this problem: An organizer would like to arrange all the participants in a circle where neighboring two students must ...
43 views

### Finding optimal paths for multiple agents

This is a real world problem, which due to some specific aspects of it I am having a hard time finding relevant literature for it. I am looking for either an algorithm, or a pointer to relevant paper(...
• 121
157 views

### Show that the decision version of the Traveling Salesman problem is in NP

Given a graph G = (V, E) with edge lengths c : E → R, and a number d ∈ R, is there a Hamilton cycle of length l ≤ d in G? Show that the Travelling-Salesman problem is contained in the complexity class ...
629 views

### Traveling salesman problem on an incomplete graph

In the standard framing of the traveling salesman problem, we're given a complete graph, meaning every pair of vertices has an edge in between them. And this might be close to accurate when the ...
• 377
39 views

### TSP algorithm with a good run-time based on properties of the graph (not just based on number of nodes/edges)?

In the worst case, the Traveling Salesperson Problem (TSP) is mostly accepted to take exponential runtime in terms of $|V|$ and $|E|$ (the number of vertices and edges respectively). But for many real-...
• 532
1 vote
68 views

### Do all NP-Complete problems run in $O(c^n)$ time, as opposed to $O(c^{n^k})$?

According to the Wiki article on NP-Completeness, NP-Complete problems can be solved in $O(c^{n^k})$ time (I'll call this EXP-POLY time). However, shouldn't the bound on all their run times be the ...
• 532
1 vote
124 views

### Bounding function for Travelling Salesman Problem

I have been studying the Branch and Bound paradigm. I came across an approach to solve the Travelling Salesman Problem using branch and bound where a specific kind of bounding function was used. I've ...
• 11
1 vote
88 views

• 159
185 views

### $k$-Opt TSP Local Search is exact when $k = |V| - 1$

I've been self-studying the book Algorithms by Papadimitriou, Dasgupta and Vazirani. I am having a hard time with a question about local search involving the traveling salesman problem (TSP). We'll ...
188 views

### $k$-Opt TSP Local Search is NOT exact when $k = \lceil |V|/2 \rceil$

I've been self-studying the book Algorithms by Papadimitriou, Dasgupta and Vazirani. I am having a hard time with a question about local search involving the traveling salesman problem (TSP). We'll ...
1 vote
196 views

### combination of traveling salesman with knapsack

I am trying to create an optimisation process for a variant of the travelling salesman problem which is combined with a knapsack problem in the following way: Let there be a set of points $P$ on a two-...
• 111
149 views

### How can i do this type of swap(4-opt) between 4 edges of a graph?

The double bridge move is a specific type of swap between 4 edges of a graph, also called 4-opt. It consists of removing 2 pairs of edges. Lets call them (I, I+1), (J, J+1) and (P, P+1), (Q, Q+1). ...
651 views

### Solving time of large TSP instances

The optimization variant of TSP is NP-hard, hence, finding an optimal tour takes $2^n$ steps for $n$ cities. According to Wikipedia, the largest instance solved so far consists of $n=85,900$ cities ...
29 views

### Complex profit optimisation problem (logistics and trading)

Problem statement There is a number of towns $\{T_1 \dots T_n\}$, a number of items $\{I_1 \dots I_n\}$ and a number of lorries $\{L_1 \dots L_n\}$. Each town $T_n$ has a market which offers a ...
98 views

### What is the exclusion-inclusion algorithm for TSP?

I was looking at the wikipedia page for the Travelling Salesman Problem and found a reference to another exact algorithm besides Held-Karp that's also $O(2^nn^2)$. Specifically: "This bound has ...
1 vote
97 views

### Using circles to determine shortest path in tsp

New to tsp and christofide algorithm pls help What if instead of using a spanning tree as described in christofide algorithm we use two or more intersecting circles of the input points to determine ...
1 vote
66 views

### Does the standard 4/3 integrality gap for TSP example work for Euclidean TSP?

The standard LP gap example for the held karp relaxation for TSP min $c^tx$ $x(\delta(S)) \geq 2$ $x(\delta(v))=2$ $x \geq 0$ Is to have two triangles and three long paths connecting the ...
• 83
31 views

### Traveling Purchaser Problem exact algorithms

how you doing? Im here to ask for you help. Im writing my bachelor paper as an implementation/review of the TPP algorithms out there. Almost every paper that I read references the Ramesh algorithm, ...
1 vote
119 views

### Euler Tour in Christofides Algorithm

The penultimate step of the Christofides algorithm in solving the TSP asks us to find an Eulerian tour of the subgraph formed by uniting the MST of the original graph and MPM of a subgraph. I ...
1 vote
90 views

### Covering Salesman Problem (CSP) polynomial reduction to the TSP

I am facing one problem that consists in polynomially reducing the Coverging Salesmen Problem (CSP) to the Traveling Salesman Problem (TSP). So, let me first define the CSP. The CSP, I am working on, ...
1 vote
37 views

### Heuristics for a variant of the traveling salesman problem

I am looking at a variant of TSP in which rather than visiting every node, there is a given collection of (possibly overlapping) subset, and the salesman must pass through one node from each subset. ...
124 views

### Traversal algorithm for an optimal item collecting route in the game "Eternal Return: Black Survival"

I am currently trying to implement a algorithm for the game "Eternal Return: Black Survival" as a kind of exercise in Rust. Since the game may not be familiar to many, here is a quick ...
239 views

### Nearest neighbor algorithm for TSP when triangle inequality holds

The output given by this nearest neighbor algorithm for the Travelling Salesman Problem can be arbitrarily bad. In the example constructed here, the triangle inequality doesn't hold in most cases. Let ...
240 views

### Can the "closest neighbor" algorithm get arbitrarily bad in TSP?

Let's consider the following simple algorithm for attacking the Travelling Salesman Problem: Choose the pair of cities $(A,B)$ where $A\neq B$ and the distance between $A, B$ is minimal amongst all ...
1 vote
47 views

### Delivery problem, unsure which exact problem it is

I'm looking for guidance on how to reduce the following problem to a known problem or a suggestion for solving it altogether. Optimal / heuristic solutions or any other suggestions are greatly ...
• 51
119 views

### A paper claiming that optimization version of symmetric TSP can be solved in polynomial time

In the following paper : Czopik, J. (2019) An Application of the Hungarian Algorithm to Solve Traveling Salesman Problem. American Journal of Computational Mathematics,9, 61-67. In the Introduction, ...
65 views

### Is this variation of the traveling salesman problem NP-hard

Consider the following setting. You have $n$ cities, and there is a cost to travel from a city $i$ to a city $j$ given by $c_{ij}>0$ where $c_{ij}\neq c_{ji}$. Moreover, if you are traveling to ...
1 vote
59 views

### CVRP and removing edges from a graph

I am solving a CVRP (Constrained Vehicle Routing Problem) on a connected graph, that is not necessarily complete. Edge weights represent Euclidean distances. I know that, in general, the complexity of ...
608 views

I have a directed graph $G=(V,E)$ where each vertex is a 4-D coordinate $v: (x, y, z, c)$ representing spatial coordinates $x, y, z \in \mathbb{R}$ and the non-physical parameter colour $c \in (c_{1}, ... • 123 1 vote 1 answer 126 views ###$P = NP\$, what am I missing?

First post here so hope I'm not missing too many guidelines. I've had this idea for a few weeks now and I can't myself see where I'm going wrong with it, hope it makes some sense to you and thanks in ...
• 13
1 vote