English subtitles

← 14-02 Sloppiness

Get Embed Code
1 Language

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

  1. In the last unit, we have talked about how if we encounter a problem
  2. that is NP-complete, we can often, using very advanced algorithms,
  3. still hope to find a solution for those problems, at least in practice.
  4. Because you learned about techniques such as intelligent search trees and preprocessing.
  5. Now, in this unit we're going to investigate something different.
  6. So consider a challenging problem such as measuring the length of an elephant.
  7. Now, doing that exactly is actually not that easy because the elephant might be moving
  8. and it might not like the ruler down here.
  9. So finding an exact solution such as the elephant has a length of 5.107 meters
  10. might actually be quite a difficult thing to do.
  11. On the other hand, if you allow for a bit of sloppiness, and say,
  12. "Well, let's just estimate it at about 5 meters,"
  13. then you can get a solution much faster.
  14. What we're going to look at in this unit is if sloppiness,
  15. or at least allowing for a bit of leeway, can actually help us solve
  16. NP-complete problems more efficiently.
  17. And what I mean by sloppiness is the following: Let's say we wanted to solve shortest tour.
  18. What we always asked was, very demandingly, what is the shortest tour?
  19. No excuses, no leeway, no sloppiness. What is the shortest tour?
  20. And what would happen now if we didn't ask what is the shortest tour,
  21. but rather asked the following: What is a pretty short tour?
  22. So for example, 20% within the optimum.
  23. Then we become less demanding on what the algorithm is supposed to produce.
  24. And now, of course, the question is, will this allow us to construct faster algorithms?
  25. Now, before we dive into this, I would like you to quickly think about this approach for a bit.
  26. In which scenarios might a sloppy, or not-exact solution be acceptable?
  27. So what I would like you to think about for a little bit is,
  28. in what scenarios approximation to the best possible solutions would be acceptable?
  29. So approximations is the more formal term for sloppiness,
  30. and, of course, just to be precise, in this unit we're
  31. going to be dealing with optimization problems.
  32. You can also talk about approximations to decision problems,
  33. but that's a bit of a different scenario, and, actually,
  34. we'll get into that when we talk about randomization.
  35. But this is not part of this unit here.
  36. So would we be content with approximations if the stakes are low,
  37. so we're solving an approximation problem where nothing is really critical?
  38. I mean, you might spend a little bit more money,
  39. but it's not going to mess up research or anything like that.
  40. Would it be acceptable if the algorithm kind of sounds good?
  41. We do not have a provable guarantee, but it still appears
  42. to yield good solutions and make sense in general.
  43. And would using an approximation be acceptable
  44. if we find that exact solutions are simply out of the question?
  45. We're using the best search tree; we're using preprocessing,
  46. but still our instances are so large, and they behave so badly
  47. that we just cannot find an exact solution.