CS 627 – Advanced Algorithms (Winter 2026-27) · unit page · YouTube
2026-11-12, 11:55

Click any sentence to play from there.

The transcript was generated automatically by YouTube's speech recognition and is offered as is. It may contain errors, in particular in concerning technical terms, names and formulas.

0:03 After we've seen how to prove that probably an problem has no FPT algorithm, I want to come back to some algorithmic techniques. We've seen simple ones like kernelization and depth-bounded search.

0:17 But there's a bit more that you can do for uh getting FPT algorithms and maybe more interesting algorithms as well. And uh we'll we'll dip our our toe in this here. Uh so there's a bit of an umbrella unit for showing a few nice things and treat that outline as potentially evolving. Uh what we'll start today is with the rough idea of linear programs so that you have an intuition at this point. Uh linear programs are optimization problems, which means you have some variables that can take numerical values. In the sense in the case of of linear programs is continuous or real values. And there's an objective function. We'll come to these the terminology later again. You're trying to optimize a certain function that depends on these variables. And there might be some some side conditions, some constraints that tell you what values are are allowed.

1:22 Uh it it is known even though uh the simplex algorithm doesn't do it, it's known that linear programming in general can be solved optimally in polynomial time in the worst case. Uh the method that would would do this the first is the ellipsoid method and some interior point methods are known to also give this result. Uh this is something we'll just appeal to as a black box. Uh I won't get into these uh worst-case polynomial time algorithms. What I want to convince you of is that it's a useful tool for both theory and Uh for theory, because you can always say if you formulated your problem as a polynomial-size LP, a linear program, then you're done proving that the problem is in P. Is in P. Okay. This should be a bit clear about saying this. Um it also means that likely this algorithm that you get there is maybe not the fastest you can build, but not horrible either.

2:29 Usually linear programs, even with a lot of variables and constraints, are still feasible to solve in practice. Uh interior point methods seem to be on the sweet spot of both, but this is a family of algorithms. Um there's still, I think in practice, dominant algorithm for most cases is the simplex algorithm, which is the historically oldest as well. Um and the practical aspect is is exemplified by the many solvers that do this really well out of the box. Um I'll I'll prepare some collab with an example for next time where you can see that it is indeed very easy to use as well. You don't need much uh setup for that. And for for LPs, the open source solvers that are out there are essentially so good that the edge that the commercial ones have is not that much. Uh this will be different for integer linear programs. We'll come to that. As a little toy example, let's suppose the following classic operations research question.

3:38 You want to maximize your profit. What else? You're uh a Hessian apple farmer. Hessian. So um uh Hessian James. Uh do do people still know Does that ring a bell, Hessian James? Okay. Uh maybe that's something for um the off off-topic channel.

4:02 Then uh just treat as as what it is. Uh is an example of operations research. You want to grow these these heirloom varieties of apples and you've narrowed it down to two varieties of apple trees.

4:23 Uh the trees have different yields of apples in terms of the money you can get to sell them for. Uh you have a certain orchard with a space. You have the space that one tree needs and uh they have some a need in terms of fertilizers and effort for harvesting them. Obviously these numbers are just made up. But uh I think it's indicative of what operations research questions can look like. And you have some some constraints on how much you can uh spend your time and how much fertilizer you can buy. Again all of these are uh not to be taken very serious, but they are indicative of what it could be like. Um the first step will be to just show this uh as a as a informal graphical procedure, how to solve such a thing and why why it may even be possible to solve it efficiently. Uh the question of course is I want to maximize my profit, but what are my variables?

5:26 I can decide how much of each variety I plant. So I can buy uh a certain proportion of these of these tree varieties. I also need maybe to plan ahead how much I will need to to harvest them and how much fertilizer and how much space and so on. There's a a lot of moving points in principle. But the things I can control are the varieties of apple I grow. The rest is following from that.

5:56 Okay. You can write this as a linear program in the following way. You first state your goal, the objective function. We want to maximize in this case. Could also be minimized in general. And now we have a function. And this is depending on two variables. The variables are how much of and how much of you buy. Conveniently named S and K so that hopefully you can remember which is which. Uh the profits that you get is 195 * S + 155 * K because that's what they give as yield. That's what you want to maximize and then there's constraints. So you say subject to. You cannot maximize these by just increasing S and K to infinity, but rather there's a space constraint. Each tree needs 4 square meters and the orchard has a certain size. Uh they have amounts of fertilizer that they need and you can only buy 3,000 kg. That was the limit.

7:06 Uh there's a certain time you need for harvesting them. 1 hour here, 3 hours here for some reason. And of course you don't want to plant a negative number of trees.

7:17 Uh LPs tend to have this property that they give you if you're not careful nonsensical solutions. Uh that's the usual way how people write such a linear program and you give it a name on the side if you want. So this is this can look like. And for solving this, okay, terminology first. Uh we have variables. This is a bit boring. Shall we do that next time? Let's first do the picture. I'll do the terminology next time because we'll then build on it uh from there onwards. We have two variables, so I can still draw this in the plane. So on the x-axis I have S, on the y-axis I have K. Uh there will be both non-negative, so above the this is not even not even shown, but we know this, right?

8:12 In this upper right quadrant, there's a constraint that gives me how much space I have in the orchard. And so, of course, I'm I I want to be on this side of this line below in the space. I have some time for the harvest that gives me another line and I have to be below. I have the fertilizer which turns out to be much more stringent than the orchard. Right, so everything needs to be in this below area.

8:40 So the feasible region is this polygon. Any point in there corresponds to an amount of that you can buy and plant so that all the constraints are satisfied. So far so good. Where's our profit? The profit is a line with a certain slope because the two trees have a different outcome. So, for example, you can put it here at 50k gives you the line here. Any point on that line gives you that profit. And the line segment in the whatever that color that is, light rose color region is a feasible point where you would earn that profit. But there's no reason to stay there. You can move this line around and you can increase your profit until you eventually hit the region where you leave the feasible region. So the best way here turns out to be this vertex. The the the point where the two constraints, the harvest and the fertilizer constraint are simultaneously tight.

9:53 At that point, you receive the optimal solution, the optimal profit of 155.5k, whatever. Okay? And then, of course, you can read off the x and y coordinates give you how much you should build, how how you should buy and and plant. And in this case, uh, you already see potential problem, but uh, take it for now as it is. Um, the harvest and fertilizer constraint are precisely tight, so you'll spend every single free minute on harvesting your apples and you'll buy exactly that amount of fertilizer, whereas you'll leave a lot of space in your orchard free. That's just life.

10:37 Uh, which maybe tells you where you might make more profit if you are able to lift some of these constraints. Maybe you can scrape up a few more uh, pounds of fertilizer somewhere.

10:50 Okay. That's going to be the gist. Um, what you see in the picture immediately is everything is linear. The constraints are just lines because they're linear inequalities. The objective function is a line because it's a linear function. Uh, so that's the defining property of of a linear program that I didn't stress on this slide. Each of these lines here has to be a linear function of the variables. So it's some constant times one variable plus another constant times another variable, sum of all the variables. That's true for the objective function and it's true for all the constraints. In this case, we had less or equal, greater equal constraints. There we can be a bit more variable, we'll see.

11:42 And the graphical way for solving this is just let this line slide up until it leaves the region and then uh, that's the manual version to solve it.

← Video 5-4: W[1]-hardness reductionsVideo 6-2: LP Basics & Terminology →