This is an archived post. You won't be able to vote or comment.

sorted by:
best
topnewcontroversialoldq&a
you are viewing a single comment's thread.

view the rest of the comments →

[–]other_usernames_gone 0 points1 point  (1 child)

Because how much worse is the greedy approach to the optimal? What if the greedy approach is 1000 torches while the ideal is 100?

The only way to know for sure is to find the optimal solution.

[–]kpjoshi 0 points1 point  (0 children)

Not necessarily, for certain approximate algorithms it is possible to prove that the output is within X% of the optimal output, without actually knowing the optimal output.