Questions tagged [traveling-salesman]

The Traveling Salesman Problem and variants

Filter by
Sorted by
Tagged with
0 votes
0 answers
26 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 ...
Mathematician....'s user avatar
0 votes
0 answers
82 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 ...
Alex D.'s user avatar
0 votes
1 answer
32 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 ...
Jewel Paresh Limbochiya's user avatar
1 vote
1 answer
126 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 ...
TheCollegeStudent's user avatar
0 votes
0 answers
27 views

Upper bound of traveling salesman problem via dynamic programming

For a set of $n$ cities, the total time to compute OPT (see Fomin & Kratsch, Chapter 1) is given to be \begin{equation} \sum_{k=1}^{n-1} O\left(\left(\begin{...
Jung's user avatar
  • 101
0 votes
0 answers
11 views

Are there any good papers that provide good definitions for the Minimum Weight Hamiltonian Path Problem?

I am looking for a paper to cite in a paper of my own regarding the Minimum Weight Hamiltonian Path Problem. This is distinct from the TSP because it is a path, not a cycle, meaning that a return to ...
Darcy Sutton's user avatar
-1 votes
2 answers
54 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 ...
Darcy Sutton's user avatar
-3 votes
1 answer
48 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? ...
Aditya's user avatar
  • 115
0 votes
1 answer
55 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 ...
Emily's user avatar
  • 1
0 votes
1 answer
46 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) ...
Rohit Pandey's user avatar
2 votes
0 answers
72 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 ...
Russ's user avatar
  • 121
0 votes
1 answer
81 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 ...
Anonymous Molecule's user avatar
2 votes
1 answer
40 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(...
Itamaram's user avatar
  • 121
0 votes
2 answers
105 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 ...
akerman's user avatar
0 votes
1 answer
353 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 ...
Rohit Pandey's user avatar
3 votes
0 answers
37 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-...
chausies's user avatar
  • 512
1 vote
0 answers
60 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 ...
chausies's user avatar
  • 512
1 vote
0 answers
59 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 ...
Rayan's user avatar
  • 11
1 vote
1 answer
77 views

Reducing euclidean TSP of smaller size to euclidean TSP of bigger size

Assume I have a euclidean TSP solver that is optimal, but it can only solve inputs with exactly $N$ vertices. Let's call it the N-solver. Now, I have an input with $K$ vertices in the 2D plane, where $...
Luigi Efour's user avatar
0 votes
0 answers
17 views

How to plot the 'back-to-home-city-path' in TSA without repeating cities

I'm doing an implementation of the traveling salesman problem using genetic algorithms, but I can't get it: If we need to get the best route in a certain set of cities and then go back to the first ...
deniable_encryption's user avatar
0 votes
1 answer
120 views

approximation ratio of TSP problem where the weights are bounded by an inequality

Consider a variant of the TSP problem where the cost function $c$ is not only symmetric but also satisfies $c(u, v) ≤ 2c(u, w) + c(w, v)$ for arbitrary vertices $u, v, w ∈ V$ . Give a polynomial time ...
SVMteamsTool's user avatar
1 vote
1 answer
66 views

Why DFS transversal without the duplicates is a valid cycle?

So I am studying apporiximation algorithms for TSP problem and there is a step that I don't get. Essentially trying to solve TSP means we are looking for a minimum cost Hamiltonian path. The well-...
tonythestark's user avatar
4 votes
1 answer
207 views

Approximation ratio on (1, 2)-metric Travelling Salesman Problem (TSP)

I encountered a problem, where I am given a (fully-connected) graph within a metric space, where each edge weight is either 1 or 2. My task is to prove that the following greedy algorithm gives a $\...
NiRvanA's user avatar
  • 159
3 votes
1 answer
134 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 ...
Fimpellizzeri's user avatar
4 votes
1 answer
168 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 ...
Fimpellizzeri's user avatar
1 vote
0 answers
126 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-...
Carpet4's user avatar
  • 111
0 votes
1 answer
119 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. Let`s call them (I, I+1), (J, J+1) and (P, P+1), (Q, Q+1). ...
Matheus Soares's user avatar
0 votes
2 answers
410 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 ...
Nepomuk Hirsch's user avatar
0 votes
0 answers
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 ...
Harold Cavendish's user avatar
2 votes
1 answer
65 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 ...
tricky_labyrinth's user avatar
1 vote
0 answers
85 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 ...
Ken Clemmer's user avatar
1 vote
0 answers
65 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 ...
Hao S's user avatar
  • 83
0 votes
0 answers
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, ...
matheus's user avatar
1 vote
1 answer
93 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 ...
Jake Andrews's user avatar
1 vote
0 answers
77 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, ...
Matheus Diógenes Andrade's user avatar
1 vote
1 answer
33 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. ...
Davis Yoshida's user avatar
0 votes
0 answers
95 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 ...
418 teapot's user avatar
0 votes
1 answer
159 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 ...
Dominic van der Zypen's user avatar
0 votes
1 answer
190 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 ...
Dominic van der Zypen's user avatar
1 vote
0 answers
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 ...
Mike's user avatar
  • 51
0 votes
0 answers
100 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, ...
watcher54's user avatar
0 votes
1 answer
60 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 ...
FeedbackLooper's user avatar
1 vote
1 answer
49 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 ...
Michele Bolognini's user avatar
2 votes
1 answer
551 views

Shortest path given correct order of colours?

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}, ...
batlike's user avatar
  • 123
1 vote
1 answer
120 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 ...
Simon's user avatar
  • 13
1 vote
1 answer
210 views

Clarification for binary search in solving optimal TSP when a polynomial algorithm with a budge exists

Below is Question 8.1 in Algorithms by Dasgupta et al. There's a solution to this problem that uses binary search from here. Pasting the answer for posterity. My questions are: When they say input ...
heretoinfinity's user avatar
1 vote
1 answer
275 views

Why is crossing paths bad in Traveling Salesman?

I'm learning about Traveling Salesman in an online course (sorry I can't share the link it's paid only) and the first step to solving it then just state "as a heuristic we avoid crossed paths&...
user8714896's user avatar
0 votes
1 answer
134 views

Reducing the Hamiltonian cycle to the travelling salesman problem and self loops

If this is my adjacency matrix for the hamiltonian cycle: $$\begin{pmatrix}0&1&0&1\\ 1&0&1&0\\ 0&1&0&1\\ 1&0&1&0\end{pmatrix}$$ Then a reduction ...
Essam's user avatar
  • 155
2 votes
0 answers
142 views

Why should 3-Opt be used over 2-opt for solving TSP?

I know the working of 2-opt and 3-opt local search algorithm. But I could not find any example where solution improvement is not possible using 2-opt but 3-opt. I am looking for a proper explanation ...
Ayaz49's user avatar
  • 121
0 votes
2 answers
115 views

Route finding on a graph that must go through multiple edges

I have this graph It shows a graph of a map that has nodes and segments (or edges), with weights, that connect these nodes. Some of these segments have addresses on, and some of these addresses are ...
Adam Cole's user avatar

1
2 3 4 5