English subtitles

← 14-03 Sloppiness Solution

Get Embed Code
1 Language

Showing Revision 1 created 10/03/2012 by Amara Bot.

  1. And, of course, this is 1 of those easy intro quizzes just to
  2. get you thinking a bit about approximation.
  3. So it's clear, when the stakes are low, yes, approximate solutions are acceptable.
  4. If we gain running time, why not?
  5. If the approximation is very good then usually those solutions are also acceptable.
  6. The important thing that I wanted to emphasize is that, in this case here,
  7. I said that we have a provable guarantee on how good the algorithm is.
  8. So we'll not get into ±1%, unfortunately, in this unit,
  9. but what we will be doing is, we will be analysing approximation algorithms
  10. to see how good they really are.
  11. Because the thing is this: Approximation algorithms, where you have not done the analysis
  12. and they just sound good, can actually lead to very, very bad solutions,
  13. and I'll show you 1 example for vertex cover in this unit.
  14. So using approximation is okay, but you have to do the analysis nevertheless
  15. to see how good that approximation will be.
  16. Otherwise, you can walk into some rather nasty traps, I would say.
  17. And finally, whenever an exact solution cannot be obtained,
  18. yeah, of course, then we have to try an approximation if the problem is important to us.
  19. The important thing here, that I would like you to keep in mind, is what we found out in the last unit:
  20. that often it is possible to find exact solutions for NP-complete problems and practice.
  21. So many people tend to start out with approximation algorithms
  22. once they hear that a problem is NP-complete, and actually, I would like you
  23. to think about this the other way around.
  24. So first of all, NP-completeness can definitely mean that there still is a possibility
  25. for finding exact solutions, and only when that approach fails, or you're under time pressure,
  26. or there's no really good known search tree for your problem,
  27. and you have to solve it nevertheless.
  28. Only then would I like you to think about approximation.
  29. So I guess my message is this: Whenever you encounter an NP-complete problem,
  30. be demanding an exact solution unless you really know it's not possible.