Harvard University · 1:24:33 · https://www.youtube.com/watch?v=Jsg9TwLRTbM
1. Primal-dual ski rental
0:00 Okay, I'll get started. Uh, so today we're going to finish off more examples of the primal dual method to develop good online algorithms. Um and then hopefully if we have time we'll start uh something else, namely approximation algorithms. Okay, so I promised you last time that we're going to again take another look at ski rental.
0:29 So, cost of renting is $1. Cost of buying is $b and I think you're scribing today, right? Is that right? Okay. Um and we saw deterministically you can get a two approximation. I mean uh two competitive algorithm online. Okay, so now I'm going to show you a randomized algorithm.
1:00 The bound that I'm going to show you is originally um so today we'll get a randomized um randomized algorithm with competitive ratio Okay, so the competitive ratio is going to be roughly e over e minus one. But to be more precise, it's going to be one plus one over one plus b one plus one over b to the b minus one.
1:46 Okay. And as b gets large um notice that as you know, when b is large one plus one over b to the b is roughly E. Okay. So, this is roughly 1 + 1 over E - 1, which implies that this thing is roughly E over E - 1 as B gets large.
2:18 Okay, so this thing is always at least E over E - 1, but it converges it goes down toward E over E - 1. And the the worst case is when B is 1. When B is 1, this will give you 2. Which um B is certainly at least 1.
2:32 Otherwise, you would never bother renting. Okay. So, this bound is uh due to Karlin and others. Um Karlin et al. Algorithmic '94. But today, I'm not going to show you the result the way that they did it. I'll show you today you will see you will see a primal dual view of uh getting this bound.
3:21 And this Um so, you know, you can see this book uh by Bookbinder and Naor. So, they introduced in '05, I mentioned last lecture, this primal dual approach of getting good online algorithms. Um and then they wrote a book, I believe in either '07 or '09, I can't remember, that uh gives this as one example amongst many others.
3:51 Okay. So, remember that
2. Formulating the LP
3:55 Remember the model. Okay, so we have a covering LP. Um and we see the constraints one at a time, and if the constraint's not satisfied when we see it, we have to make an online decision to change some of the variables to satisfy it. And the variables that uh throughout throughout time, the variables have to be monotonically non-decreasing.
4:14 Okay, so let me remind you, we did this last time, what the LPs are. So, for ski rental, we have the primal LP, which says minimize Bx plus the sum I from 1 to K Zi. Okay, so Zi tells us whether we rented on the ith day, and X tells us whether we've bought uh the skis, and there are K days.
4:42 Of course, we don't know K ahead of time. And there are the constraints. One constraint is that for all days I, we had to either have rented or bought. And also, uh X is at least zero, and for all I, Zi is at least zero. So, this is a covering LP. And then we have the dual.
5:16 Okay, so remember in the dual, um constraints in the primal turn into variables in the dual, and the right-hand side in the primal turns into the objective function in the dual, the thing that you dot product with. So, you get max sum I from 1 to K of Yi.
5:36 So, you have one variable for every for every day, such that Okay. Such that uh the sum I from 1 to K of Y I is at most B. And also that for all I uh I think 0 is less than or equal to Y I is less than or equal to 1. Okay?
6:15 So, the way we're going to do this is we're going to online build up both the primal and dual solutions. Okay? Um and they're both going to be We're going to maintain that they're both feasible. And we're going to say that the objective uh cost on the primal solution we find is not too much bigger than the dual. Yeah.
6:38 So, is there any way to intuitively describe what the Y I represent after Um let's see. Right. So, for us, as we build this, Y I is either going to be 0 or 1. Um so basically, Y I is going to be 1 for the Y I is going to be 1 for the days where we rent.
7:14 And then it's going to be um and then it's going to start being 0. So, it signifies that you rented on that day, sort of, but not I mean there are no integrality constraints here, so yeah. Okay. Yeah, I mean, we will see in a in a in the next example when we do set cover. Um we will see that well, actually not then.
7:43 When we do approximation algorithms and we analyze um, set set cover approximation algorithm, there will be a more intuitive, uh, way of thinking about the Y's. Okay.
3. Online algorithm design
7:59 So, uh, here's going to be our algorithm. Initially, X, uh, all ZI, and YI are zero. Okay. When we see, uh, constraint, so what what what are we seeing online? We're seeing these constraints online. Every day we see a new constraint X + ZI is at least one. So, when we see constraint I online, um, if X is already equal to one, do nothing.
9:04 Okay. Otherwise, we're going to set ZI to be 1 - X. We're going to set X to be 1 + 1 over B X + 1 over CB. C is a constant that I'm going to choose later. And we're going to set YI to be one.
9:48 Okay. So, what do we need to understand? We need to understand what's the ratio between the objective functions in the primal and the dual. And we also want to ensure that X and Y are both feasible. Or the primal and the dual solutions are both feasible. Okay.
10:11 So, first off, um let's bound the primal ca- the primal objective over the dual objective. Well, in every step of this, they either both don't change, okay? Or the dual objective changes by one. It It increases by one. And how much does the um how much does the primal objective change by?
10:51 So, in every step, uh the change in the dual objective At every step, okay? So, either both objectives don't change, or the change in the dual objective exactly equals one cuz we increment YI by one. And the change in the primal objective. Well, what's the change in the primal objective?
11:39 Um it's B. So, right? There's this B here. B times the change in X plus ZI. Okay? And what's this? What's the change in X? Well, this is B times the new value of X is 1 + 1 over B X plus 1 over CB.
12:20 And the old value of X was just X. And this X cancels that X. So, this is So, this whole thing um this whole thing is uh X + 1 over C. And then when you add in the ZI, and then this let's say this is plus ZI. When you add in the ZI, remember ZI is 1 minus X, so this is 1 plus 1 over C.
13:03 So, the primal objective over the dual objective is at most 1 plus 1 over C, namely 1 plus 1 over C divided by 1. Okay. Good.
4. Competitive ratio analysis
13:24 So, now we just need to say that this thing is feasible or that X and Y are feasible. Okay, so let's look at the primal. Now, ZI is just 1 - X. So, that's exactly that's a tight constraint. And certainly, we never make anything negative.
13:47 So, the primal is seen to be feasible. Okay. How about the dual solution that we're building up? Well, definitely all the YIs are between 0 and 1. But then there's this constraint that we need to ensure happens. Okay? So, so primal feasibility is just immediate.
14:14 And then we have dual feasibility. We need to We need to ensure that the sum I from 1 to K of YI is at most B. Okay. Well, how many what How many times do we set YI to 1? Well, we do that as long as X is less than 1. Right?
14:43 Once X is 1, we don't do this else condition. So, we just need to make sure that we we we can only be in this else clause B times. We need to show can only have X less than 1 at most B times.
15:13 Okay? So, let the increment to X on the ith day be xi. In other words, I mean X is the sum over I of xi. All right, so X X starts off as zero, then we add some amount X1 to X, then some amount X2 to X.
15:42 So, you can so it's not hard to convince yourself from this formula that first of all, X1 is 1 over CB and the xi are geometric with ratio Q being 1 + 1 over B. This implies that the sum
16:17 from the first day to say the B minus first day of xi is equal to 1 over CB times the sum I going from uh sorry, to the Bth day, I guess. I going from let's say J going from zero to B minus 1 of Q to the J. Okay.
16:52 And this is equal to 1 over CB times What's Q? 1 + 1 over B to the B minus 1 over uh Q minus 1, which is 1 over B. B cancel. Uh that B cancels that B. And this is equal to uh 1 + 1 over B to the B - 1 over C.
17:38 Okay. And what did I want What did I want? I wanted that after B days, X is going to be 1. So, I'll now I now I'll choose C. So, set C equals 1 + 1 over B to the B - 1.
18:03 Okay. So, that's it. We have a 1 + 1 over C uh competitive ratio. And uh C is this, which is exactly what I promised you. And now X and Y are both feasible. And what's the point? The point, remember, is that
18:20 in general, you have that um any dual solution, so let's say uh uh cost of the dual is always at most Let me call that cost of D, D for dual, is always at most opt of the primal is always at most cost of the primal, where this These are feasible solutions.
18:45 So, cost of the primal, I mean, for any feasible solution. Okay? And we just said that the cost of the primal is at most uh 1 + 1 over C cost of the dual. Right? So, now you can bring this opt over here. This implies that the cost of the primal solution we found is at most 1 + 1 over C times opt of the primal.
19:12 So, we're 1 + 1 over C competitive. Okay. So, are we done? Do I now have a 1 + 1 over C competitive algorithm for ski rental? It's not integral. The ski rental problem says every day I mean, what does this mean? Like I'm every day I'm buying some fraction of the skis and I'm renting some fraction of the skis. That's not actually a valid uh ski rental solution.
19:51 Okay? And you know, as you you and I haven't used randomness anywhere. I told you I'm going to give you a randomized algorithm.
5. Randomized solution
20:01 Okay. So, how are we going to actually get a valid integral randomized solution? Well, this is the ratio I want. So, as you might imagine, what I'm going to do in my randomized algorithm is somehow get this in expectation. Okay?
20:20 So, problem. We can't fractionally rent or buy on each day. We must be integral. So, the fix is going to be using randomization. And how do we do that? So, the randomized algorithm, okay, the randomized algorithm that I'm going to tell you is going to actually main- is is going to actually maintain that, okay, in its memory.
21:20 But it's going to do something first. So, the first thing it's going to do is so initialize all of XZI and YI to zero as before. But it's also going to pick at the very beginning just a random number uniformly at random.
21:48 Okay. And when seeing new constraints we we will update the X and ZI and YI as before fractionally. Okay. But now we need to choose are we going to actually rent or buy? So, we have these fractional solutions lying around. Do we rent or buy? We buy.
22:27 So, here's going to be the picture. When do we decide to buy? So, I think it's easier to just draw it. So, here's Here's the the interval from zero to one. We pick the random alpha. Alpha, you know, happened to be here, let's say. And X, remember I defined these XIs, these increments that happen.
22:57 So, So, this is not Chuck. Okay. Um So, first we increment X by some amount X1. Then we increment by some other amount. Well, let me This is X1 here. Then we increment by some other amount X2. Then we then X3. Then uh X4.
23:29 Remember and and X is just the sum of the XIs. When do we buy? We buy on the day that alpha landed in. Okay? So, here we'll buy on day four. Okay? So, now let's analyze our expected cost of doing this.
24:24 The expectation of the cost Well, the cost is just the sum of money you spent buying and the money you spent renting. So, that's the expectation of money spent buying plus the expectation of money spent renting. Okay? So, So thing here So now the expectation of the money I spent buying That's just equal to B times the probability that I buy.
25:13 And if What's the probability that I buy? Well you know, let's say X is the sum of the Xi. So X X is right here. So the probability that I buy is the probability that alpha is less than equal to X, which is exactly X. Okay.
25:42 And what's the expectation of the money spent renting? Well, that's by linearity of expectation linearity of expectation, that's the sum over all I of the probability Well, the you know, you can define an indicator random variable for whether or not you rented on day I. And then the total number of days you rented is just the sum of those indicator random variables.
26:12 Okay. And the expectation of one of those indicator random variables is just the probability that you bought. So this is the sum over I of the probability that or or rented, sorry. The probability that you rented on day I. What's the probability that you rented on day I?
26:34 Well alpha has to be less than X1 X2 X1 + X2 + dot dot dot up to Xi - 1. Okay. So this is equal to the sum over I um Sorry. Sorry. So if alpha is less than that, it means you buy, you don't rent. So alpha has to not be less than that.
27:12 So it's 1 minus that. So 1 minus 1 minus X1 + X2 + dot dot dot + Xi - 1. But this is just what X was at that point in time. So this is 1 minus X at that point in time, which is exactly Zi. So what do you know?
27:45 Our expected cost is B times X plus the sum of the Zi, which is exactly Did I erase it? Which is exactly the primal objective. So in expectation, we achieve the primal objective. Okay? So we get So now we actually do have our uh We actually do have our close to E over E minus 1 competitive algorithm.
28:10 All right? Questions about that algorithm? So like the day is chosen in advance. Yeah. Yeah. Yeah. Yeah. That's That's right. Because the way we update X, right? I mean, the way that these x i's are deterministically defined, so uh once we once we pick alpha in the beginning, we know when we're going to buy.
28:56 That's right. Any other questions? You look like you have a question or no? I think it's just why why is it x i? Why do we call Um Should it be x i? If we rent it on day i, so let's say so the probability of renting on day i is the is one minus probability of buying on day i. So, what's the probability that we buy on day i? Well, at the beginning of day i, we haven't done the increment to x yet. Yeah.
29:44 So, for example, thing of day one, day one x at the beginning of day one x is still zero. And then we add the increment in the else. In the else. Um but certainly even if I mean, even if you even if I somehow am off by one, if you added an x i here, that would only uh help you cuz then you'd be at most c i, so. Okay.
6. Set cover introduction
30:18 Okay, so I want to show you one more example of a primal dual uh online algorithm. All right. So, here I want to look at set cover. And the algorithm the the bound that I'm going to show you is due to Alon, Our Book Zar, Bookbinder and Naor.
31:05 This is SICOMP '09. Okay. So, let me refresh everyone's memory and introduce some notation for set cover. We have a universe so the problem definition So, we have a universe of elements one up to n. And we have m sets S1 up to Sm.
31:52 Each one is a subset of the universe. And our goal and let's also Yeah, our goal here okay, let me write this out. Our goal pick sub collection of the Si covering the universe. Okay. Their union should cover the universe. So, Any questions about the problem definition?
32:35 So, I haven't said anything about online, but this is what I mean by set cover. So, what's online about this? What's online is that So, we know that there are these M sets. In the beginning, we know there are M sets, S1 up to SM. But, we don't know anything about what they contain.
32:54 Okay? And online, we see elements. And when we see an element, uh so, the person will tell us which sets contain this element. And now we have to If we're not If we haven't already picked one of those sets into our set cover, then we need to choose a set right there and then to cover it.
33:15 Okay, so we see elements online and must immediately cover them. Okay, so that's online set cover. Who Who has Who has seen set cover at some point in their lives? Who has not seen set cover at some point? Okay.
34:02 So, Who has not seen NP-hardness, the notion of NP-hardness? Okay, people have seen NP-hardness, good. So, set cover is an an NP-hard problem, meaning that unless there's some huge breakthrough in computer science, we're not going to We don't expect to have a polynomial-time algorithm.
34:24 Uh Okay, so for that reason, I claim that at least if our online algorithm is efficient, you know, we're not going to hope to get uh Oh, and furthermore, again, not not only is it not only is it NP-hard to solve set cover exactly, but it's even hard to approximate.
34:49 Meaning that if I give you the entire set system in the beginning, there's no online here, it's an offline problem, and I say find me the best set cover, it's hard to find a set cover that's you know, uh better than a log n approximation of the optimal set cover. Okay.
35:07 What do you mean by optimal set cover? Small, yeah. So, you want to find you want to find some set cover that's not worse than alpha times the best in terms of size of subcollection. So, beating So, beating alpha being log n is a hard problem. Yeah. Uh number of sets or size of the individual sets? Log uh log n approximation.
35:27 So, number of sets though. Like, if you have So, yeah. Uh what do you mean? Well, I mean, you could like Like, let's say you have two sets which are both missing one, that's better than like having a bunch of large sets that are disjoint. If you have two sets that are both I'm I'm just asking what the optimality condition is, right?
35:43 O- Okay, so you must you must cover all the elements. That's a requirement. you could optimize either for fewest number of sets or little overlap. Fewest number of sets. Yeah. Okay, so that was my question. Yeah. All right, right. And I I guess I didn't say that. Minimize number of sets taken in your subcollection.
36:09 Okay, so if we're efficient online, we don't expect to do better than a log n competitive ratio. You know, if otherwise, we would have a better offline uh Just pretend that this things came online even though they you know everything. Okay, so um we'll show online uh log log n times log m competitive ratio.
36:43 Okay. First, I'll show you I think in in both cases, the algorithm will actually be the same. But first, I'll show you a purely primal view. Uh and we can and you know, we can prove correctness just for this primal view, but then I'll show you um then I'll show you a primal dual view as well.
37:06 Okay. Okay, good. So, let's write uh an LP relaxation for the set cover problem. So, primal So, we're going to have one variable for every set. Um so let me So, let's let me just write this uh m set. So, we have a collection C of sets, which is S1 up to Sm.
37:57 Where Si is a subset of 1 to n. Okay, so the primal, we're going to have one variable for every set, and we want to minimize the number of sets taken. So, we want to minimize the sum over S in our collection of x of S.
38:19 And normally, x s has to be um either zero or one, but we'll we can't enforce integrality in linear programming. If you enforce integrality, that becomes integer programming, which is NP-hard. Okay, you can encode, for example, 3-SAT as an integer program. So, what are the constraints?
38:39 So, for every I in N, we have a constraint that says that the sum over uh S containing I of XS has to be at least one. And furthermore, X coordinate-wise has to be non-negative. You could say, you know, we could also have a constraint saying X has to be at most one, but that's not necessary because no optimal solution would make any XI bigger than one. Okay, that's the primal.
39:21 There's the dual. Remember, we have one variable for every constraint, so we have one variable for every I. So, this is maximize the sum over I from one to N of YI. And for every variable, we have a constraint. So, for all sets S in the collection, we have a constraint which says that the sum over I in S of YI is at most one.
39:58 And we also have the constraint that uh Y is at least zero. And that Yeah, okay. Oh, this doesn't matter so at most one again doesn't matter so much cuz this already sort of enforces that. Okay, good.
7. Primal view of set cover
40:29 So, just out of curiosity, who here has not seen any differential equations? Ever? Oh, okay, good. So, yeah, maybe you thought, you know, maybe when you learn equations you thought why would I ever never use diffy Q's? I'm going into field X which uh where that doesn't appear.
40:54 So, this we're going to use diffy Q's. Okay, so but not not anything too fancy. You'll see in a second. So, what are we going to do? We're going to maintain as usual uh primal We're going to maintain uh primal and dual solutions.
41:10 And we're going to show that we can get um feasible solutions for both where the objectives are not far off from each other. Okay, this is the usual game. So, the algorithm Remember, we know the thing that's coming online are the elements. Okay, not the sets. We know the set so we're going to we know that there are M of them.
41:37 Initialize X to be 1 over M everywhere. And now what comes online? One of these constraints comes online. An I comes in. Okay? And I might not be covered. Okay? So, if I is not covered, so meaning this constraint is not satisfied, so right now I'm not going to show you I wrote the dual up there, but I'm going to show you a purely primal way of looking at things before I go move to the primal dual.
42:20 We're not going to maintain anything about Y right now. Okay, we'll just do work in the primal. What I'm going to do is as long so when we see constraint I Okay, while suppose I is in some sets S I 1 up to S I K or S I R or something.
43:00 I don't want to use I twice. S J 1 up to S J R. So if if this constraint is already satisfied, we're done. If it's not satisfied while constraint is not satisfied we'll run a continuous process where um X S changes according to uh over time.
43:50 Imagine like imagine that there is some time unit. And the way that we vary X S with time is that D X S of T D T is X S of T. Okay? So, uh run this process simultaneously for all of these j all of these s's sj1 up to sjr until the constraint becomes tight or until the constraint is satisfied.
44:51 Okay. So, the solution to this I mean this is the we're not doing any fancy diff eq's. The solution to this differential equation is just e to the t. Okay. After it's t times steps it become e to the t. Uh but so um after excess evolves for t time steps it multiplicatively increases by a by e to the t factor.
45:32 Okay, I could have I could have just said uh multiply all of these by e to the t for the smallest t which satisfies uh the constraint. But uh there are there are some fancier examples of covering LPs where
45:49 uh it Well, first of all I mean this time thing is going to you'll see in the analysis this this view of things running for continuous time uh is going to you know, help us understand what's happening. Okay, so now definitely definitely the the primal solution we end up with.
46:11 I haven't said anything about the dual. The primal solution we end up with at the end of everything is feasible. Right? Because we run we run this for time until it's actually satisfied. So everything is satisfied and nothing ever becomes negative. The The question is just how can we argue that our competitive ratio is not that bad?
46:30 Okay. So I want to compare to opt somehow. So this constraint is not satisfied. But opt is satisfying this constraint. Right? So in particular and what which sets are we incrementing? We're incrementing the excesses which contain which contain I. One of those has to be in opt's solution.
47:07 Right? So every time we run this continuous time process we're incrementing we're evolving someone who's in opt. Whenever we run this evolution some set in opt is increasing. Now if you focus for one particular focus on one particular set in opt how long how many time how many seconds can it or time steps can it evolve?
47:56 in this process. Right? So, what is all the excesses start at 1 over M? And we would never bother evolving anything unless a constraint was not satisfied. Right? So, the fact that the constraint is satisfied, oh, maybe I should maybe I should also say this. Um Yeah, so if a constraint is not satisfied, right?
48:28 It means that that set in opt is less than one. Okay? So, how many time steps can any set in opt be evolved for? Natural log of M. No set in opt evolves for longer than log M seconds. Right?
49:10 So, the total number of seconds that were ever in this evolution phase is at most opt times log M. Like over the entire course of the algorithm. So, the algorithm runs this process for at most opt times log M seconds.
49:42 All right, that's all nice. But, what is the amount of time that we run have anything to do with uh being good compared to opt? Well, what's the derivative of the primal objective as a function of time with respect to time? Okay?
50:14 So, the only part of the primal objective So, this is equal to the derivative of X S J1 plus plus X S JR dt. Right? Cuz the other variables aren't changing. What do I know about this sum during the evolution? I'm evolving because the constraint is not satisfied.
50:53 Right? So, what does that mean? Yeah, it's at most one. This sum is at most one. Right? So, first so the derivative of this with respect to time is exactly according to our differential equation, it's exactly S X J1 of t plus dot dot dot plus X S JR of t.
51:17 But, this is at most one. It's less than one. Otherwise, we wouldn't have bothered evolving. Okay? Now, the objective starts off at one. Right? It starts off So, X starts off as one over M everywhere. So, our our primal objective starts off as one. And the way that it changes over time is every time unit, it increments by at most one.
51:49 It increments by at most one in every time unit and it only runs for opt times log n log n time units. So, that implies at the end of all of the algorithm the primal objective is at most opt times log n.
52:18 Okay. So, we have a log n log n competitive. Or are we? Again, it's not integral. Okay. So, yes. But Yeah, it's better. Yeah. Yeah. In fact, I should say that um in that paper, they show that not only can you achieve this, but you cannot achieve better by by more than log log factors.
52:53 So, that's um up to log log, that's basically the right answer. Um Yeah, so I guess Yeah, if you're also Yeah, if you're looking for final projects, you can investigate this removal of the log log. I I I think they I think there's a gap of log log, but uh Yeah. Okay.
53:10 So, again, we have the same problem. This is not an integral solution, you know? We have to at at every time step, we have to actually take some set. Right? Some of the What One of the x's has to actually be set to one. We can't just keep them as fractions.
8. Primal-dual set cover
53:36 So, before I fix that, you know, I want to give a primal dual view. Um actually I should investigate I should check that paper more carefully. This paper came out the the conference version came out before it came out in '03 which is before Bookbinder and Naor did the whole primal dual view of online algorithms.
53:57 So, I didn't actually uh I haven't didn't actually read the paper but I think they only did this primal view of things. They didn't do the primal dual view. I think. I mean otherwise the time doesn't make sense. So, let me show you the primal dual view. So, this is uh this is all the purely primal view.
54:18 We never talked about the dual. So, how about the primal dual view? Okay, so we'll maintain the excesses as before. Okay. But we also want to maintain Y's. So, Y is initially set to zero. And as we run evolution to satisfy the ith constraint we also evolve YI according to the differential equation d YI of t dt is one.
55:32 In other words, every second YI goes up by one. Okay. So, already we see that already we see that the primal objective in every time step is going up by at most one. The dual objective, right? The dual objective is just the sum of the Y I's. The dual objective in every time step is going up by exactly one. This already tells us that
55:59 um at the end of the day when we get our X's and Y's, our primal and dual solutions, um the cost of X is at most the cost of Y. The primal cost of X is at most the primal cost of Y. Okay.
56:16 Now, that tells something is a a little off, it sounds like, right? Because if the primal is feasible and the and the dual were feasible and the primal is at most the dual, well, we know that the dual is always at most the primal. That would just say primal equals dual, which says we got the optimal thing. So, the catch is that this dual is not going to be feasible.
56:38 But, what we're going to show is that if we scale the dual down by log M roughly, then it would be feasible. Okay, and that that's going to be good enough. So, X, just like before, is feasible. We already talked about that. X is feasible. So, the claim is that if you take Y and entry-wise you just divide by log M, that's dual feasible.
57:14 Feasible for the dual program. Okay, proof. I mean, basically, what what does that mean? We need to show need to show that for all S in the collection the sum over I and S of Y I is at most ln M. I mean, we need to show that this constraint is is only unsatisfied by a ln M factor.
57:51 Right? Then that would give it to us. Well, why is that the case? Well, let's focus on a particular set S. All right. Now, look at this sum. If sum Y I is being increased in this sum, we're also simultaneously increasing X S for every S that contains I.
58:24 So, whenever this sum is increasing, we know that X S is increasing. But, we already talked about this. How long can X S possibly increase? ln M seconds, right? Cuz then it becomes one, and then we would never run the evolution again. So, that's it.
58:52 Whenever sum of Y I I and S increases, um we know X S is increasing. And this is increasing at a rate of exactly one at every time step. So, after ln M time steps, this is exactly ln M. We know X S is increasing. And X S can only increase at most ln m time steps.
59:39 So, that implies that sum over I and S y i is at most ln m. So, if you divide by ln m, it's feasible. So, what we just showed we just showed that again uh the cost of y i of the cost of y over ln m
1:00:12 is at most the dual cost is at most opt of the primal is at most uh the cost of the primal on x and which we know is at most the cost in the dual of y. Right? And this is this cost is linear, so this is just 1 over ln m times the cost of y.
1:00:40 Right? So, that implies exactly what we want. That implies that just bring this opt over here. That implies that the cost the primal cost of this x that we found is at most ln m times opt. Okay, great. So, I mean we didn't do anything different.
1:00:57 We Well, I mean we didn't get anything new. We just saw a primal dual way of looking at it. In the purely primal way, we compared directly with opt. In the primal dual way, we never really talked about what opt was. We just built a dual solution. Okay, so now let's talk about actually fixing this thing.
9. Integral set cover solution
1:01:52 So, kind of the first attempt is The first attempt So, first let me write you know, getting an integral solution. So, the first attempt would just be at the very beginning for each S in the collection pick uniformly random alpha sub S in zero to one.
1:02:55 Once X sub S uh is bigger than alpha S, so maintain the fractional solution just like we were doing. Once that fractional solution on S is bigger than alpha sub S take take it into the into the collection. Take uh S into our solution.
1:03:20 Just to be clear, that doesn't mean we set XS to one. Okay? We're going to keep the fractional solution running just as it ran before. Just on the side, we're going to maintain the sets that we're actually going to output. Okay?
1:03:35 So, when when we decide to take S into the solution, that means we're going to output S as being one of our sets, but we're still keeping X sub S the fraction that it was before. Okay? So, that we can still say we can still say that our fractional solution is giving the same cost as it was before.
1:03:53 Okay, so one thing you can show, which is basically the same thing we did last time, is that the expected cost of this integral solution is the cost of the fractional solution. Okay? I'm not going to do that computation, but it's roughly the same as what we did before with ski rental.
1:04:30 But, there's a problem. What's the problem? Huh? Might not be feasible, exactly. Okay? At least with ski rental, if we if we didn't randomly decide to buy, we were always renting anyway, so we're always feasible. Here, if we mess up and we don't actually take it into the solution, then that element's not covered, and this might not be feasible. And there are gust sequences.
1:05:23 And so, what's the fix? So, for this fix, I'm going to um I'll assume that you at least know N. All right. You know, you can actually remove this assumption. Maybe I'll put it as a homework thing, I don't know. Or maybe I'll put in the notes. Um but let's say you know N, you just don't know what's contained in what.
1:05:49 So, the fix is So, what's what's really going on here? So, we know from the primal feasibility that So, view these View XS as now being the probability that we actually put S into our solution, right? So, this sum is like view it as the number of the amount at the amount the point I is covered, the number of times I is covered.
1:06:12 What this is saying is that the expected number of times I is covered should be at least one. Okay? But if you And then if you randomly put things into the set with this with this probability, then there's some unfortunately some chance good chance that you won't actually cover it. So, the trick is just to boost it.
1:06:33 So, rather than say rather than have it be that the expected number of times we cover the element is one, make the expected number of time number of times we cover the element log N. Okay? So, the fix is um once XS is bigger than equal to alpha S over some big constant times log N, then take S into the solution.
1:07:15 You look troubled. Are you troubled? No? There's still some probability that we won't satisfy. Yeah, there is. It's just going to be small. Okay? Um Wait, wait. Is that really what I want to do? No, no, no, no. Sorry, this is not This is not what I want to do. It's a good thing you're troubled. You should have been troubled. Yeah.
1:07:48 I sensed I sensed uh Okay. So, So, this is the This is the actual fix. For each S, we will pick alpha S one, alpha S two, up to alpha S R in 0 1 uniformly at random and also independently. And also R will be, you know, some big constant times log N.
1:08:38 Okay? And then, if XS is bigger than or equal to alpha S uh J for any J, then put put S into our solution. Okay. Good. So now our expected cost um increases by at most an R factor, which is why we get I don't know if I erased it.
1:09:28 This is why we get a log n times log m competitive ratio and R times log m competitive ratio. And if you look at any element, the probability that its constraint is not satisfied for any one of them, let's say that the probability that its constraint is not satisfied due to alpha s1 is at most some constant, a half or something.
1:09:53 So the probability that none of them satisfied it is exponentially small in R, which is one over poly n. So by union bound, they'll all be satisfied. There are only n of them, right? So if the failure probability is one over poly n, then um by union bound, our failure probability of not being feasible is one over poly n.
1:10:13 So that's that's it. Yeah. It seems like we could do something that like wouldn't fail at all by just like for each n Yeah. a random like zero to one and then subtracting it from Um Wait, say it again. Cuz it seems like for each for each n, right?
1:10:51 The probabilities I mean like add up to one, but they don't. Yeah, it doesn't work if you're not mixing it correctly. So if you sample something from like zero to one, Uh okay, so so one thing that's worrying about me about this this like deterministic rounding without So, I mean, are you going to lose a log n in what you're doing?
1:11:16 Okay, so so so so one thing about one thing about set cover is like you know, for the offline problem one way to solve one way to to get a good algorithm for set cover is Did I erase the primal already? Maybe I erased the primal. You solve the primal.
1:11:32 That gives you probabilities for each set. And then, you know, you and then you round up then you take the set with probability equal to X of S. Okay? That gives you a randomized algorithm for set cover. And you run into the same issue that it might not be feasible, so you blow things up by this log n. Okay?
1:11:48 So, for set cover, we know there's there's a a proof that you cannot beat a log n approximation unless um I think unless P equals NP. Okay? So, um if you So, yeah, so that's why I'm a little cautious about deterministic rounding which doesn't lose anything. Okay, so I have about 10 minutes left.
10. Approximation algorithms
1:12:17 Um I guess I'll set things up for next time. So, we're done with primal dual online algorithms, and I want to move into um a new but related topic. So, uh so the next uh topic is uh approximation algorithms. Okay?
1:12:46 So, what's that all about? So, the the basic gist of things is we have some uh optimization problem. We want to minimize or maximize something, for example, set cover. Okay? And now we're not online anymore. This is all offline, okay? So we're all offline now.
1:13:25 And the best-known algorithm for solving this optimization problem is slow. Okay? So maybe the problem is NP-hard, and the best algorithms we have are exponential time. Or maybe we do have a polynomial-time algorithm, but it runs in time n to the 10th or something. Okay? So the best the best-known algorithms are are slow. So maybe the problem is NP-hard.
1:13:59 Okay, so and that's actually the the This is the one we're going to focus the most on, approximation algorithms for NP-hard problems. And we would like to give um a fast algorithm, or at least not as slow as the one we uh as this exact algorithm, which gets a cost that's guaranteed to be within some small factor of the true of the the best cost.
1:14:22 Okay, so we want an algorithm, a fast algorithm, I should say, a fast algorithm, which produces solution with cost at most, let's say, some alpha times opt. Where alpha is hopefully small. This is for a minimization problem. If our optimization problem is a maximization problem,
1:14:59 then we would like to find a solution that has a value at least, you know, at least alpha times opt, where alpha is less than one. At least half of opt or something. And So, since um since we were just doing primal dual with online algorithms,
1:15:34 um you know, I will I'll start off with with an example here of using the primal dual method to get good approximation algorithms. So, we're not online anymore, we're offline, but we can still use the method. And in fact, primal dual the primal dual method for approximation algorithms is much older than the primal dual method for um online algorithms.
1:15:54 At least the thing I'm going to show you now is from the '70s. So, uh if you want to see more about approximation algorithms, I mean, uh you know, you can see this book. There's a book on approximation algorithms by uh uh Vijay Vazirani. It's called Approximation Algorithms. So, so this class is a kind of a broad advanced algorithms class.
1:16:20 I'm not going to there are classes that exist in the world where all they do in the entire semester is approximation algorithms. Okay? But, uh as you've already seen, that's not going to happen here. But, I will uh talk a little bit about it. Okay, so let's look back at set cover.
1:16:52 Okay, so Now we know all the sets, we know the universe, we know which sets contain what elements. We just need to get the best the smallest sub collection of sets. And I'll even give them costs. So sets
1:17:08 set S has some cost CS want to to minimize the sum over uh S chosen of C sub S while uh covering the whole universe. So before our C sub S's were all one. Okay, so I look at this primal dual primal dual approach.
1:18:21 So I think So for people who um took CS 124 with me and I think even when Professor Mitzenmacher taught it, I think he did set cover. Um if the CS's are all one, there's this greedy algorithm. I mean, you can run the greedy algorithm for other CSs where
1:18:38 at every step as long as there is an element that hasn't been covered yet, you choose the set which covers the most uh uncovered elements so far. Okay, so there's a there's a corresponding greedy algorithm which I'll tell you very soon for the cost the one with costs.
1:18:55 But so what's the primal? The primal is minimize the sum over all sets S of CS * XS. XS tells us whether or not we took the set. Subject to the constraint that uh for all I in the universe the sum of XS for S containing I is at least one and X is at least zero everywhere.
1:19:22 And the dual we have a variable for every constraint. So max the sum over uh I from one to N of Y sub I such that for all sets in the collection um the sum of I in that set of Y sub I is at most the cost. And also uh Y is non-negative everywhere.
1:20:08 Okay, so what's what's the greedy algorithm? As long as there exists uh an uncovered element we will put S into our solution such that S minimizes the ratio between its cost versus the number of elements that are that it covers. The number of new elements S covers.
1:20:56 Right? So, this is exactly the generalization of the uh of the greedy algorithm when the costs are one. So, let's do I think I have time to actually do the analysis of this cuz it's very short. So, let's do a primal dual analysis.
1:21:28 So, initially X and Y are equal to zero. When we take some set some set S we set that means we set XS to be one. And we're also going to set And also for each newly covered For each newly covered uh I and S we'll set Oops, we'll set YI to be the cost of S over um the number of newly covered elements at this point.
1:22:41 Okay, so when when we take a set S, we set XS to be one, which means we just increased the primal objective by the cost of S. And for all the newly covered eyes, we set YI We basically make the YIs share this cost.
1:23:06 So, for each newly covered element, we set its YI to be the cost of S over the number of them, which means they share it, which means that the primal and dual costs are exactly the same in these solutions we're building. Okay, so the primal and dual costs are equal.
1:23:24 Now, the primal is obviously feasible, but the dual will not be feasible. Okay, we're going to see that next time. This dual, you know, the dual constraint is that this sum must be at most CS, but just as before, we're going to vi- every one of these constraints is going to violate this by at most a certain multiplicative factor, which is going to be log n, by the way.
1:23:48 Um so, therefore, we'll when we scale down, we will get a feasible solution, and that will give us that will tell us that this greedy algorithm is a log n approximation. Okay? Um so, by the way, this approach of violating the dual feasibility and then scaling down,
1:24:04 okay, that's called dual fitting, maybe if you want to know uh if you want to know a name to Google in your future. This is called dual fitting. This art of uh of violating feasibility and scaling down. Okay, so that's it.
1:24:22 Remember Pset 3 is due I think Monday night.