## ← 14-03 Sloppiness Solution

• 1 Follower
• 30 Lines

### Get Embed Code x Embed video Use the following code to embed this video. See our usage guide for more details on embedding. Paste this in your document somewhere (closest to the closing body tag is preferable): ```<script type="text/javascript" src='https://amara.org/embedder-iframe'></script> ``` Paste this inside your HTML body, where you want to include the widget: ```<div class="amara-embed" data-url="http://www.youtube.com/watch?v=7QN2IGqrKzU" data-team="udacity"></div> ``` 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