Video 10-1: Motivation & Definitions

0:03 In the last big part of advanced algorithms, we'll look at approximation algorithms. The the big other thing you could compromise on apart from maybe the time or being deterministic. Uh you could compromise on the quality of the output. uh is very very natural in many optimization problems and it's a very practical approach and again we'll see um many different types of of techniques that are somewhat uh generic. We'll see them on concrete examples, but often they're a bit more general. And uh we might this time only very briefly touch on the complexity theory side of proving when approximations are hard to get or what exactly is is not easy to get. Uh but we'll focus a bit more on the positive side of things.

0:56 In this first um unit, we'll cover the basic definitions and look at some uh simple first examples. in particular vertex cover and set cover uh as kind of a they're not toy problems that's unfair but problems to illustrate some techniques on. Then there's a a cool notion about um approximation schemes where you can tell the algorithm how accurate you want it to be and then it'll take more time if you want more accuracy and we'll look at a few uh famous examples and then um we'll build on this in the next unit with um linear programming based techniques which really go very very well handinhand with approximations. Uh but for now the more elementary techniques And uh first a bit of um where are we and how how can we formalize what an approximation really is. So just a short recap for the notation that we've had very very long time ago. Um we had this class of NP optimization problems and uh a problem u is um as uh as you see well we'll see the components in a second uh it's a collection of instances concrete instances so u could be the problem vertex cover a concrete instance could be a specific graph then for every instance we have potential solutions feasible solutions So for vertex covers it would be all vertex covers all subsets of vertices that cover all edges. And we have a a cost function that assigns to each feasible solution some cost. Vertex cover would be just the cardality of the set. And uh we assume that we can check in polomial time whether a certain uh instance is a valid encoding of an instance whether a given uh feasible solution or well whether a given thing is indeed a feasible solution and uh we can evaluate the cost of a feasible solution.

3:00 Uh we'll here always make the assumption that the costs are rational numbers so we don't get into questions about how to represent real numbers. I think for all the problems we'll we'll discover we'll we'll discuss here um that's not really an interesting distinction.

3:22 And also remember we have two optimiz two two problem variants. The optimization problem is the more natural that we often want in applications. We want the actual feasible solution that optimizes the cost. But we can sometimes uh first design an algorithm for the evaluation problem where you only get the quality of the solution but not the solution itself. Uh in many cases you can easily get both but it's is cleaner just to first formalize the evaluation problem. We'll sometimes do that.

3:54 The whole idea of of approximation is this famous old saying. Um if you want the perfect optimal solution that might be hard but if you want to get a job done then you may have to compromise a little bit on on uh your perfectionism. So the key thing is what does that mean to be good enough? And so there's a a few terms that I want you to to use consistently. Uh a uristic is really just any algorithm that gives you some feasible solution for a problem but probably uh no other guarantee. This doesn't mean that the uh algorithm always produces bad solutions or in the worst case bad solutions. It might just mean we don't know of a guarantee that we can prove and sometimes that's all we can all we can get. Um, but the goal here is something provable. And so, uh, if you if you think about it, maybe you've seen the definitions before, but if you think about it abstractly, it's not so clear what what really you want here. Uh, you want close uh you you want a good enough solution, but what does that mean?

5:09 And the specific notion that we'll look at is compare the cost of the solution that the algorithm outputs to the optimal value. So opt in this chapter will always be the optimal objective value of the underlying problem. So again goal is minimum or maximum, right? It's just a way to unify the two kinds of problems. And then we uh we go over all feasible solutions and take the costs cost of those and optimum is uh the best possible cost. And so if we can somehow relate the output of our algorithms or the cost of the output of our algorithms to the optimal cost, that's what we call approximation. And to make it quantitative, we look at the ratio. Okay, that's in short what we do formally. So u here's the full thing as we had it back then. That's an optimization problem. It has some encoding alphabet for the inputs and for the outputs and it has uh what is allowed as an input? What are the instances we really care about? What are the feasible solutions? What's the cost of feasible solutions? And do we min or max uh in in our search?

6:29 Okay. optimal objective value or a problem u on a given instance x is written like this and we'll skip those parameters when they're clear from the context any other algorithm that's consistent with you which means whenever uh this just means a of x is always in m of x the algorithm always produces a feasible solution of arbitrary equality in in general and we call the approximation ratio of an algorithm A on an instance X just this this ratio of the cost of the algorithm divided by the optimum and hopefully the optimum is never zero kind of I think always costs are positive in the examples we look at uh for minimization problems this means that this ratio will always be above one because you can't do better than optimum and so you'll be bigger than the optimum you most of the For maximization problems, it's the other way around. Here again, you have to somehow uh check what the definitions are. If you look at the literature, this is not always consistent.

7:37 Sometimes people always take the reciprocal so that the values are always above one. But I think this is more standard these days. Okay. Then an approximation algorithm. Finally, the key definition of this of this part is an algorithm or a C approximation is an algorithm where the ratio is uh at most C or at least C depending on on the uh direction of optimization. Well, let's focus on minimization problems. Then our solution that we output is at most C times as expensive as the optimum solution of that specific instance. And so that seems to be the most convenient definition to always compare with on that specific input. What's the best you can do? Now why why the ratio and not something else? You could have said uh it's the optimum plus something or apply any other kind of function. Um I don't think there's there's a clear answer to that. It turns out that the ratio gives you a somewhat sound theory and is often a useful kind of intuitive way to say you're at most 10% worse than the optimum but this is not written in stone. Sometimes uh for for few examples of problems it can be more convenient to do some different function but that's the standard definition. That's what we we mean by an approximation algorithm.