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

1. Title:
   14-02 Sloppiness
2. Description:

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