1
$\begingroup$

Take the nearest neighbor algorithm for the traveling salesman problem as an example. Why is it used to find the upper bound? When can't it guarantee an optimal solution?

(Thanks to many comments below, which suggest (and are invalidated by) the last update of this question)

$\endgroup$
  • 1
    $\begingroup$ Lower bound for what? The Kruskal's algorithm I know solves the minimum spanning tree problem exactly. $\endgroup$ – j_random_hacker Nov 8 '18 at 11:16
  • 1
    $\begingroup$ I don't know what "NNA" is. Please try to give a bit more context. $\endgroup$ – j_random_hacker Nov 8 '18 at 13:11
  • 1
    $\begingroup$ In any case, perhaps I can answer without having to have a concrete example. It sounds like you are asking, "Why is it useful to get a quick, approximate answer to something?" If that is what you're asking, I think the answer should be apparent from everyday life: You often don't need complete precision, and paying for that (in computation time) is not worthwhile. (You probably don't bother to weigh a carton of milk in your fridge to determine whether you need to buy more milk today; you just pick it up, and if it feels "emptyish" you will buy some more.) $\endgroup$ – j_random_hacker Nov 8 '18 at 13:15
  • 1
    $\begingroup$ @SebastianNielsen What is NNA? If NNA = "Nearest Neighbor Algorithm", in the context of TSP, it doesn't provide a lower bound. It provides an upper bound. $\endgroup$ – mhum Nov 8 '18 at 18:07
  • 2
    $\begingroup$ Despite my question, you still haven't explained what "NNA" is, leaving it to other commenters to guess. 'Do we agree that the term "lower bound" means the best optimal solution (the lowest possible cost) for a route in a given graph?' This is the first time you have mentioned graphs or routes in them! But more importantly, no, lower bound doesn't mean that. A lower bound is any number that is less than or equal to an optimal (globally lowest-cost) solution. Since it (finally) transpires that you are talking about TSP: heuristics give you upper bounds, which are similarly defined. $\endgroup$ – j_random_hacker Nov 8 '18 at 18:37
1
$\begingroup$

There are lots of NP-complete problem where no algorithm will find an optimal solution - during your lifetime. Given the choice between a greedy algorithm that finds a solution quickly which is often good, and an algorithm that will find a guaranteed optimal solution, but not while you are waiting for it, what are you going to use?

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

In (one formulation of) the traveling salesman problem, you're trying to find a path that's as short as possible while still hitting all nodes.

An approximation algorithm will give you a path that hits all the nodes but is not necessarily the shortest. You know, however, that any optimal solution can't be longer than the approximation - the optimal solution has to be at least as short as every solution, including the approximation.

Since the optimal solution can't be longer than the approximation, the approximation is an upper bound: "I've found a path of length 5. That may not be the shortest path, but I know that a shortest path can't be longer than 5."

| cite | improve this answer | |
$\endgroup$

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.