0
$\begingroup$

Do one have to define the upper and lower bound to be able to solve the tsp, or is that just an unnecessary intermediate step? And if so, why would one define those bounds? (context: the traveling salesman problem (TSP))

Additional question: After having calculated the upper bound (using eg. the Nearest Neighboor algorithm), and the lower bound (using eg. kruskal's algorithm) ... let's say we get: [4; 8]

Can we say for sure that the cost of the optimal route is a number in the interval [4; 8]? Is it possible to find a route whose cost is not within the interval?

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ I don't >have< to solve the traveling salesman problem at all. Your question seems to be missing some context. $\endgroup$
    – David Richerby
    Nov 8, 2018 at 20:55
  • $\begingroup$ @DavidRicherby I am sorry in what sense? My question is in other words: Do I have to define the upper and lower bound to be able to solve the tsp, or is that just an unnecessary intermediate step? And if so, why would one define those bounds? $\endgroup$
    – Ryan Cameron
    Nov 8, 2018 at 21:44
  • $\begingroup$ I don't really understand your question. Can you give an example of the phenomenon you're trying to understand? $\endgroup$
    – Yuval Filmus
    Nov 8, 2018 at 22:17
  • $\begingroup$ @YuvalFilmus eg. do you have to do this to find the upper bound: youtube.com/watch?v=wRvQSLtRnz0 Why do people do that? $\endgroup$
    – Ryan Cameron
    Nov 9, 2018 at 13:51
  • $\begingroup$ Can you summarize the video? $\endgroup$
    – Yuval Filmus
    Nov 9, 2018 at 15:11

1 Answer 1

Reset to default
1
$\begingroup$

If you want to compute X (whatever X is), then you just need to compute X, and whatever intermediate results are required by your method for computing X. If your method doesn't need upper and lower bounds, there's no need to compute them.

The point of upper and lower bounds is that they're usually easier to compute than the actual answer, and they may be enough to answer your question. For example, as a typical student, you don't need to know the exact price of a helicopter to know that you can't afford one: helicopters surely cost at least \$100,000 and you don't have \$100000. Conversely, if you're a millionaire, you don't need to know the exact price of a chocolate bar to know that you can afford to buy one: surely a chocolate bar doesn't cost more than \$100 and you definitely have \$100.

Can we say for sure that the cost of the optimal route is a number in the interval [between the lower bound and upper bound]?

Yes. That's what "upper bound" and "lower bound" mean.

Is it possible to find a route whose cost is not within the interval?

Again, by definition of "lower bound" and "optimal", no route can be shorter than any lower bound on the length of an optimal route. Depending on what upper bound you use, it might be possible to find a route that is longer than an upper bound on the optimal route. For example, on upper bound on the length of a TSP route is to say that, since the optimal route must leave each vertex exactly once, the total length can't be longer than the sum of the longest edge from each vertex. But, if you think about it, that's actually an upper bound on any route, whether the route is optimal or not. So it's not possible to exceed this upper bound. However, it's possible that you could come up with a smarter upper bound such that the optimal route is definitely not longer than your bound, but suboptimal routes might be.

Improve this answer
$\endgroup$
4
  • $\begingroup$ I think I am getting it. But are you sure about your claim that: "The optimal route must leave each vertex exactly once, the total length can't be longer than the sum of the longest edge from each vertex." Depending on the vertices' weights, I can imagine that it might be optimal to actually visit one vertex twice. $\endgroup$
    – Ryan Cameron
    Nov 9, 2018 at 18:10
  • $\begingroup$ @RyanCameron The definition of TSP says you visit every vertex exactly once. $\endgroup$
    – David Richerby
    Nov 9, 2018 at 18:16
  • $\begingroup$ Wiki: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city and returns to the origin city?" - there is no constraint to visit each vertex once, which makes sense as that could potentially result in the salesman not being able to travel the shortest possible distance because he is not allowed to traveling back a road he has already traversed. $\endgroup$
    – Ryan Cameron
    Nov 9, 2018 at 18:20
  • 1
    $\begingroup$ @RyanCameron That's just the informal description at the head of the article. The precise statement is at "Description: As a graph problem": "... starting and finishing at a specified vertex after having visited each other vertex exactly once." $\endgroup$
    – David Richerby
    Nov 9, 2018 at 18:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.