Maximizing Distance in the Travelling Salesman Problem: Is it Possible?

  • Context: Graduate 
  • Thread starter Thread starter sparsh12
  • Start date Start date
Click For Summary
SUMMARY

The discussion centers on the Travelling Salesman Problem (TSP) and the inquiry into finding the maximum distance instead of the traditionally sought minimum distance. Participants agree that the problem of maximizing distance can be approached by inverting the weights of the edges in the graph. This perspective aligns with the theory of computation, indicating that the fundamental nature of the problem remains unchanged despite the focus on maximum rather than minimum distances.

PREREQUISITES
  • Understanding of the Travelling Salesman Problem (TSP)
  • Familiarity with graph theory concepts
  • Basic knowledge of weight inversion in optimization problems
  • Awareness of computational theory principles
NEXT STEPS
  • Research methods for weight inversion in graph algorithms
  • Explore variations of the Travelling Salesman Problem
  • Learn about optimization techniques in computational theory
  • Investigate practical applications of maximum distance problems
USEFUL FOR

This discussion is beneficial for mathematicians, computer scientists, and optimization specialists interested in exploring alternative approaches to the Travelling Salesman Problem and its implications in computational theory.

sparsh12
Messages
12
Reaction score
0
I change the question completely. If i get an answer for this, my question would be resolved.

Everyone is obsessive of finding minimum distance in Travelling Salesman Problem, but my question is,

"Is there a way to find the maximum distance possible?"

I know it is related to theory of computation, but i don't want to get into complication of computers.
 
Physics news on Phys.org
Hi, I don't know much about the TSP, but wonder in what way the problem of finding the maximum distance differs from that of finding the minimum.
 
I don't think it changes it at all. It's the same exact thing. Just invert the weights.
 

Similar threads

Graduate Difficult to understand the solution provided in the video (travelling salesman problem)
  • · Replies 3 ·
Replies
3
Views
3K
Graduate Formulation of a linear programming model
  • · Replies 1 ·
Replies
1
Views
4K
Graduate Similarity transformation changing the determinant to 1
  • · Replies 20 ·
Replies
20
Views
4K
Pulley Problem on an Inclined Surface Using Energy Methods
  • · Replies 16 ·
Replies
16
Views
1K
Undergrad Quintic Polynomial Tschirnhaus Transform: Possible complex Bring Radicals
  • · Replies 0 ·
Replies
0
Views
3K
Undergrad Need help understanding Commuting Operators
  • · Replies 6 ·
Replies
6
Views
2K
Shortest distance along the shore and into the lake
  • · Replies 6 ·
Replies
6
Views
1K
Distance traveled by a Ball affected by friction after t seconds
  • · Replies 4 ·
Replies
4
Views
2K
Distance traveled by a particle in a transverse wave
  • · Replies 2 ·
Replies
2
Views
3K
Irodov 1.23 confusion: Calculate distance traveled and time elapsed for this decelerating particle
  • · Replies 2 ·
Replies
2
Views
1K