Video 11-7: Primal-Dual Schema

0:03 In the last section of this part, we'll look at the the primal dual schema, which is a way to use the duality and the theory of linear programming, but without invoking a blackbox solver in your algorithm itself. At least that's usually how how it ends up working. And so it's both it's both beautiful because it often gives you insights into the problem itself and leads to more efficient solutions or more efficient approximation algorithms in terms of their actual running time. So far we've been mostly focused on the approximation ratio and the algorithms range from simple greedy uristics to uh let's more let's start by solving a full LP and then rounding something.

0:51 So you could say it were uh essentially ad hoc methods maybe in hindsight justified with arguments from linear programming and uh if they rely on a solver it can be expensive. there is a way to use duality slightly more directly and um I would say against all odds the kind of best best solution often comes from the complimentary slackness conditions which are precisely the conditions where I said hold on these are true for linear programs but they're not true for integer linear programs at least the one direction uh if you have some solutions some pair of primal dual solutions that satisfy them, then great. They're simultaneously optimal and with equal objective value, but most hard problems will not do you the favor of of uh satisfying these. And so they seem to be of little use, but indeed you can make them useful um in the following sense. Uh you can consider some relaxed version of the complimentary slackness conditions and I'll show you in a second more concretely what that means.

2:02 And then we can try to somehow maintain a pair of solutions that satisfy these these relaxed complimentary slackness conditions. Um, curiously though, normally the complimentary slackness conditions start with let x and y be a primal dual feasible pair of of values and then if these conditions are satisfied that that's an if and only if that the two are optimal. Here we're going to use the complimentary slackness conditions, the relaxed versions. And it turns out the relaxed versions don't imply feasibility anymore. So we're working with um solutions that are satisfying these modified CSC conditions but are not necessarily feasible. uh you'll see how this makes a lot sense in the example but still the the general um I want to describe the general schema because it is more more more applicable than just to the example problems. So the primal solution uh will keep integral but it may not be feasible initially. For the dual we don't care about integrality but we want to keep it uh feasible.

3:16 And then we um use the complimentary slackness conditions to guide us uh where to make changes. Um, and so, uh, we're trying to make X more feasible, and that means we're going to, uh, make Y, uh, not satisfy the complimentary slackness conditions, and we let those guide us how to adjust things. Okay. Uh, it's a bit vague. Um, the cool thing about this general theme is no matter how you do it in in details, if you maintain this dually feasible Y, that's always going to be a certificate for how far away from optimum your your solution X is in the end. You have to keep going until X becomes feasible. Otherwise, it's it's nothing. It's no solution at all. Uh, but once X becomes feasible, if you've maintained a dually feasible Y, then that gives you a bound on the optimum. And so often times you can a priory guarantee that you're getting a certain approximation ratio.

4:19 Okay, let's see this in a bit more uh concrete. Uh first of all, these are the uh complimentary slackness conditions as we had them uh before. So for standard LPS and again standard LPS just to have them uh here again And so if you look at what the complimentary slactus conditions say um they're they're essentially pairing a variable in one problem to a constraint in the other problem. And remember these are from the way we dualize this is very natural that you would get this pairing because a variable in the dual let's start with this a y i here is essentially the multiplier we put on the constraint on the i constraint in the primal and vice versa because okay I never said this but if you take a problem and dualize it and dualize the dual again you get back the primal that's something I never said but it is true though nevertheless Okay. Uh so but it's natural in in this case. So why was the multiplier I think I'm always going to denote this as the primal, this as the dual. So it would help if the P wouldn't look like a D.

5:57 Um and vice versa. So x can be seen as the multiplier of the j um dual constraint and uh here this is just one of the constraints where you replace the greater or lesser equal with equality. Okay, that's complimentary slackness and the conditions say well uh there's two options how a solution can be tight and optimal. either the uh multiplier I'm I'm going I'm giving to the constraint in the primal is zero. So I'm I'm I'm going to kill that constraint uh or it's going to be satisfied with equality.

6:39 And if you think well you can you can tie it back to um extreme points and so maybe I'm not going to get into the polyhedral theory again but uh clearly um these these constraints are a stricter version of the constraints in the original problem. You replace the lesser equal with equality. So they still imply uh the original constraint. They're just more strict.

7:07 Now uh the relaxed versions that we'll look at uh they replace this strict equality here with a bit of slack. So uh I really wish we would have those on the next slide as well.

7:29 There's uh two two parameters alpha and beta. So for the two primal for the the two uh pairs of of constraints we allow a different fudge factor. Uh for the first one we take this constraint that used to be equal to C and say it's at most C but at least C divided alpha. Okay.

7:50 And so um you see that's that's still uh uh somewhat um similar still refineses this um constraint here but uh leaves a bit of slack. So it doesn't require it with equality. It requires it with a slack of alpha. Um for for the second part we also have that this um so that's a b not a zero here also you have the constraint ax greater equal b um but we don't require equality anymore just not too much uh too far away from b not too much bigger okay and the core of the primal dual schema is if you have X and Y a pair of primal dual feasible solutions and this can mean in an ILP or in an LP both works same way now uh whatever problems you're looking at if they satisfy these alpha beta relaxed complimentary slackness conditions then you get uh a quantified version of weak duality if you want um the uh the cost of the CTX is most alpha time beta times this dual cost. Okay.

9:34 and weak duality would mean that the minimization problem is greater equal this and now we're getting something in the opposite direction. So we sandwich cdx between bty and alpha beta bdy.

9:48 The proof for this is just uh from computing from the definitions uh it's relatively boring. You take cdx now you're going to use uh on c your complimentary slackness condition. this part. Um, if you multiply by a then you get this a alpha time sorry multiply by alpha you get alpha a y for z and the x is where it is. Then you uh expand the transpose. Then you have ax which you can just bound um again with uh with this one by b beta * b you replace that and then you just uh swap things around. Beta is a scala so you can move it to the beginning. Okay. um trivial proof, but the point is if you can somehow make these uh relaxed complimentary slackness conditions hold until you get some feasible solution, then you get a guarantee for the approximation ratio. Cool. Let's finally see this in action. Uh if you look at our set cover um LP and dual LP, you get the complimentary slackness conditions like this. uh either the variables is zero as always and then you have the the dual constraint we can't pack uh I think this was always an e doesn't matter but yeah uh so you kind of can't you're you're packing so the the true complimentary slackness conditions is you pack exactly as much as the capacity of that set for the primal constraint you cover uh exactly with one um in general this will not be possible to fulfill with integral solutions. So we relax it and we pick alpha is one and we pick beta to be f the frequency of the element the maximum frequency and it in this case it just makes this uh this uh second part trivial in the sense that all we're asking for here now is if you sum up all the sets where an element e occurs in its variable it should be at most f but if If you keep the xjs below one, that's always going to be satisfied because we have at most uh f sets where this occurs in. So it's kind of we're making that second condition completely trivial. Hey, that's fine. Um trivial conditions are easier to satisfy.

12:28 And in the end, we're going to aim for a factor f approximation, right? Alpha time beta is just f here. That's that's what's what's going to pop out. And then you can do um the following uh cute algorithm. That's the primal dual set cover approximation. Uh f is the global frequencies or the maximum number of sets that any element occurs in. We initialize our two solutions x and y with the all zero vector and t will be the elements part of this the universe that we still have to cover. And as long as some elements are not covered, we take some element. And now there's no no greedy uristic or something like that, but instead we take the dual variable the y and we're trying to pack more of that element. And so uh if you if you do that uh there's going to be some point where at least for some set you're going to hit this uh this constraint with equality. Right? So the y e you can make them bigger.

13:39 Um but at some point you're going to had the constraint was less or equal. At some point it will be exactly equal for some sets. Okay you keep doing for this single variable you increase it until you hit for some sets the the boundary the threshold and then you look at all those sets where this is now satisfied with equality. So these are this is the first part of the complimentary slackness condition. So if this part is satisfied that means we no longer need x to stay at zero. Remember we initialize x and y all to zero which means I should I really wish we had these on the slide. This is stupid. Let's do Let's do that chunk making sure these are always satisfied is trivial. If you say x and y are all zero, then the first part always satisfies the whole thing. But then we don't make any progress towards um a feasible x.

14:56 So we take one of the y's, we make sure that we're trying to satisfy the second part by raising y. And once it hits exactly the the upper bound, we are free to make xj to set that to one. And that's what we're doing, right? We set xj to one. We remove all the elements from t that are now covered by sj. and then we repeat. So in a way it's it's still a kind of greedy algorithm but the greed is now with respect to this dual variable and that way it's a bit more careful than the original greedy. It's also it's an f approximation not just this hn. Um well okay they're I guess in general incomparable. So we keep doing this until there's no no element left that's not covered.

15:51 And so this is an f approximation. Um and there's not much to show. The the key thing here is that the proof becomes much easier with this uh setup. The algorithm only terminates when x um encodes a set cover otherwise there would be some elements in t left. So at the end x is primary feasible. And when uh we have some some element that is included, we only include it when at the time this um the dual constraint was satisfied with equality. That's this uh CSC1 as I called it in the proof, right? Uh, so if that's satisfied with equality, now we're actually never going to change it. That would that only depends on the elements y for elements in this set. And we only ever change y is for elements that are still in t, but we've removed all the elements from sj. So this was true now and is not going to be modified. So we'll keep uh keep that at equality.

17:01 And so that means our x y pair at the end satisfy these 1 f relaxed comp complimentary slackness conditions. And so uh that's all we really need. um because uh then we can can use the previous lema for getting the approximation guarantee and here it's a factor f I guess we would need to argue that y is feasible but we keep y feasible initially and and throughout uh unlike for the primal the dual uh problem Here this bumped around weirdly. Uh the the for the dual problem setting all y's to zero is a feasible solution and so it's initially feasible. We never bump it above the capacity so it remains feasible.

18:16 And so that's a pretty pretty uh slick and short proof of this fact and a similar kind of you can apply the same uh thinking to other problems. uh it's much more versatile now if you think about it because all we need is really some some LP or ILOP representation of the problem and then much of what we've done here is is guided from the ILP and doesn't need problem specific insight apart from uh which alpha beta to pick that's the only part and that is it for approximations uh we've seen a lot of of small examples so I wanted to list the different design patterns. Again, uh there were two based on rounding. either you do some simple simple thresholding or uh you do some randomization and coupon collecting and we've seen today uh to complement those to methods that use the the duality theory of LPS either to just analyze an algorithm that we've somehow come up without or specifically from first principles start with the uh the primal and dual problems and devise an algorithm from there.

19:27 That brings me to the end of the approximation chapter and also the end of the material for for this term. So, thanks for staying till the end and uh we'll see each other for the fun lecture for enrichment next week.