Video 10-8: Randomized Approximation Algorithms

0:03 We've talked about randomized algorithms and we've been talking a bit about approximations and we will talk a bit about approximations more but you can also combine the two ideas and uh I just want to show the appropriate definitions so that um these are these are clear um and there's this two notions that can make sense a randomized approximation and an expected uh approxim approximation. So, um, we have a an optimization problem here. I'm I'm assuming it's a maximization problem. Um, and we have some uh approximation ratio delta that we we try to uh achieve and then we call a randomized algorithm a randomized delta approximation for the problem. if it always outputs a feasible solution. So that has to be with probability one and with at least probability 1/2. The solution that it does output has uh approximation ratio at most delta. So it can it can output worse solutions occasionally. It can never output infeasible solutions that are not even a valid solution. But it has to output one that satisfies the approximation guarantee uh half the at least half the time. So you can already imagine you can repeat this and boost this probability and you just always pick the the best solution that you've seen.

1:40 Uh the other notion is um where we have an expectation smuggled in. So same setup now an algorithm is a randomized delta expected approximation. Uh if again it always outputs a feasible solution and the expected value of the approximation ratio is is uh delta.

2:03 Uh of course you can define the same thing for minimization problems. It's just that you have to flip these inequalities. I didn't want to have too many case distinction. I think you can you can deal with that. Um yeah. So uh these these are these are two different notions um that you can partially also convert between uh but just so that if you see these terms you know what's what's meant