# Why are greedy algorithms used to find upper/lower bounds? (when they doesn't guarantee an optimal solution)

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)

• Lower bound for what? The Kruskal's algorithm I know solves the minimum spanning tree problem exactly. Nov 8, 2018 at 11:16
• I don't know what "NNA" is. Please try to give a bit more context. Nov 8, 2018 at 13:11
• 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.) Nov 8, 2018 at 13:15
• @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.
– mhum
Nov 8, 2018 at 18:07
• 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. Nov 8, 2018 at 18:37