
Title:
1403 Sloppiness Solution

Description:

And, of course, this is 1 of those easy intro quizzes just to

get you thinking a bit about approximation.

So it's clear, when the stakes are low, yes, approximate solutions are acceptable.

If we gain running time, why not?

If the approximation is very good then usually those solutions are also acceptable.

The important thing that I wanted to emphasize is that, in this case here,

I said that we have a provable guarantee on how good the algorithm is.

So we'll not get into ±1%, unfortunately, in this unit,

but what we will be doing is, we will be analysing approximation algorithms

to see how good they really are.

Because the thing is this: Approximation algorithms, where you have not done the analysis

and they just sound good, can actually lead to very, very bad solutions,

and I'll show you 1 example for vertex cover in this unit.

So using approximation is okay, but you have to do the analysis nevertheless

to see how good that approximation will be.

Otherwise, you can walk into some rather nasty traps, I would say.

And finally, whenever an exact solution cannot be obtained,

yeah, of course, then we have to try an approximation if the problem is important to us.

The important thing here, that I would like you to keep in mind, is what we found out in the last unit:

that often it is possible to find exact solutions for NPcomplete problems and practice.

So many people tend to start out with approximation algorithms

once they hear that a problem is NPcomplete, and actually, I would like you

to think about this the other way around.

So first of all, NPcompleteness can definitely mean that there still is a possibility

for finding exact solutions, and only when that approach fails, or you're under time pressure,

or there's no really good known search tree for your problem,

and you have to solve it nevertheless.

Only then would I like you to think about approximation.

So I guess my message is this: Whenever you encounter an NPcomplete problem,

be demanding an exact solution unless you really know it's not possible.