Video 11-1: LP & ILP recap

0:02 In the next unit, we'll stay with approximation algorithms, but we'll bring back this uh powerful tool we've looked at briefly before, namely linear programs, uh which turned out to be a very very convenient ingredient to build approximation algorithms. I'll do a quick recap in case you forgot and also to set the notation uh which certainly people will will forget over many weeks. Um and then we'll look at different ways you can use LPS for approximations. In particular, we'll also look at this duality theory of LPS that uh I left out last time and this really comes to shine in this chapter.

0:49 So just briefly to recap um we've talked about this at length in oh dear what was it unit six something like that uh a linear program and here I've already given the standard form we'll we'll come back to why that is convenient uh is a is an optimization problem of this sort you're trying to minimize some cost you have variables which can be any uh real number but non- negative. You have n of these variables and you have a linear cost function that gives each of the variables some coefficient and you have a linear set of inequality constraints where uh you can concisely write these m constraints in the matrix uh notation. If you forgot what these look like, uh here's uh what they mean unfolded. Um but we've dug through that uh back in the day.

1:50 Um yeah, terminology that we had also last time. So a feasible solution is just some some values for for x in this case that satisfies these two constraints, these inequalities. Um recall that ctx this value the objective function value and then an optimal solution is one with minimal objective function value or minimal objective value and we'll usually denote that with a little star. Uh here it's formulated to have integer coefficients in all the functions and constraints. You can generalize it to rational coefficients without much happening most of the time. uh we don't want to have arbitrary real numbers. So because we need to represent them exactly uh rational function rational numbers is usually fine. You can multiply the constraints and the cost by the uh common denominator if needed. It will sometimes make a difference though. So it's um it's important to keep in mind that uh you should say uh if the coefficients are restricted to integers or not.

3:01 That was LPS. Uh here's an example um some like a arbitrary example that doesn't have a specific meaning. uh just to make it concrete and you can work out that it has a certain optimal uh value at this at this point and optimal objective value 26.

3:25 Um we also talked at length back then about the geometric few polyhedra and and extreme points. Uh you can show that uh an optimal solution is always an extreme point where some of these constraints are met with equality.

3:41 um instead of the standard form that I've shown you, you can allow equality constraints. You can allow variables that are not just non- negative. You can do max instead of min. All these standard tricks to reformulate LPS we covered back then as well. Uh but you can assume standard form for algorithms because you can transform. Uh in general uh such a program can be infeasible meaning there's no value for x that satisfies all constraints simultaneously or it could be unbounded in the sense that you can uh improve this to infinity or minus infinity or minimization.

4:19 But the interesting case that pops out from typical optimization problems is that it is finite meaning there is some some concrete finite optimal objective value.

4:31 Okay. Um that's what I mentioned. If there's some optimal solution if it's finite then there is a an extreal point that's optimum and we can compute those in polomial time. uh in practice the simplex methods but in theory the ellipsoid method is the one that's guaranteed to be poly time worst case you know all this from back then uh just to remind people um the last bit also repetition integer linear programs are almost the same as what I've just shown except that we have a constraint that things are natural numbers uh integral as opposed to just non non- negative and that's somehow seems like a harmless change but it makes the problem nplete even so the decision problem would be is there a way to make the objective value better than the threshold um and so it makes a big difference in terms of how easy it is to solve the problems but also you can put these in standard form using essentially the same tricks