Skip to main content

Questions tagged [traveling-salesman]

The Traveling Salesman Problem and variants

Filter by
Sorted by
Tagged with
5 votes
0 answers
100 views

Minimum cost path connecting exactly K vertices

I came across a situation in real life that maps to this optimization problem: Given a fully connected, undirected, weighted graph with $N \ge K$ vertices, find the simple path connecting exactly $K$ ...
InfiniteSnow's user avatar
1 vote
2 answers
28 views

Pseudo-Traveling Salesman on a colored graph

I have a graph with nodes of various colors and weighted edges between them. I would like to find the least cost path that touches exactly one node of each color. Is this a known problem or reducible ...
Jemmy's user avatar
  • 113
0 votes
1 answer
48 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 ...
David's user avatar
  • 3
1 vote
0 answers
15 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 ...
Duda's user avatar
  • 111
3 votes
2 answers
90 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 ...
Erel Segal-Halevi's user avatar
-1 votes
1 answer
48 views

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

I`m 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 ...
Tuan's user avatar
  • 1
0 votes
0 answers
53 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 (...
Dair's user avatar
  • 244
0 votes
0 answers
38 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
94 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
2 votes
1 answer
51 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
153 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
-1 votes
2 answers
68 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 ...
Hera Sutton's user avatar
-3 votes
1 answer
67 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
108 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
74 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
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 ...
Russ's user avatar
  • 121
0 votes
1 answer
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 ...
Anonymous Molecule's user avatar
2 votes
1 answer
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(...
Itamaram's user avatar
  • 121
0 votes
2 answers
165 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
825 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
41 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
  • 532
1 vote
0 answers
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 ...
chausies's user avatar
  • 532
1 vote
0 answers
131 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
2 answers
91 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
19 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
178 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
93 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
418 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
218 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
240 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
217 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
158 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
743 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
122 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
98 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
68 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
  • 93
0 votes
0 answers
32 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
143 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
96 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
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. ...
Davis Yoshida's user avatar
0 votes
0 answers
133 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
278 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
260 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
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, ...
watcher54's user avatar
0 votes
1 answer
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 ...
FeedbackLooper's user avatar
1 vote
1 answer
61 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
618 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
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 ...
Simon's user avatar
  • 13

1
2 3 4 5