Chapter 35: Approximation Algorithms: Vertex Cover, TSP, and Set Covering

Welcome to Last Minute Lecture.

This free chapter overview is designed to help students review and understand key concepts.

These summaries supplement, not replace, the original textbook and may not be redistributed or resold.

For complete coverage, always consult the official text.

All right.

Welcome back to the Deep Dive.

Today, we're going to be looking into some really, really tricky problems.

You know, the kind that computer scientists call NP -complete.

Oh, yeah.

NP -complete.

So these pop up everywhere, right?

I mean, think about like figuring out the best way to deliver packages or even designing super fast computer chips.

And what makes them so tough is that finding the absolute best solution, like the perfect answer can take forever, like way too long to be useful in the real world.

Yeah.

You hit the nail on the head there.

I mean, it's like they're hard to solve perfectly when time is of the essence, right?

And yet they're super important problems.

So the question is like, what do we do when we need a good answer, but we can't wait for like the absolute best one?

What are the strategies?

Exactly.

Exactly.

So the stuff we're diving into today, it kind of lays out like three main ways to tackle these NP -complete problems, right?

So first, if the problem is like small enough, maybe we can just brute force it, you know, use an algorithm that takes exponential time.

But hey, at least it guarantees the best answer.

And then second, sometimes we can find like special cases, right?

Or like put some constraints on the problem that actually make it solvable in polynomial time.

So that's kind of cool.

Right.

Like special shortcuts.

Yeah.

Yeah.

But the third approach, and this is what we're going to really focus on today, is like this whole world of approximation algorithms.

Yeah.

And these are algorithms, to put it simply, that just aim for a good enough solution, you know, something we can get in a reasonable amount of time.

We're not fixated on like the absolute best answer, you know?

Yeah.

Good enough.

That's the key phrase, right?

But how do we actually like measure that?

How good is good enough?

Right.

That's where this idea of an approximation ratio comes in.

And the material we're looking at, it explains that this ratio basically tells us how close our approximate solution is to the actual like perfect solution.

So for a problem where we want to minimize something, like say finding the shortest path, you know, the ratio is like the cost of our approximate solution divided by the cost of the optimal one.

And obviously we want this ratio to be as close to one as we can get.

Right, right.

Makes sense.

But for maximization problems,

it's flipped, right?

It's the optimal divided by our solution.

Yeah.

And it's important to remember that like this ratio, it's not always a fixed number.

Sometimes it's like a small constant number.

So like we might be able to say, hey, our solution will never be more than say twice as bad as the best one.

Right.

But other times it might like grow depending on how big the problem is.

Right.

Right.

It scales.

Yeah.

And there's also this trade off we can sometimes make.

Like we can spend more time computing to get a better approximation, you know, a solution that's closer to the optimal one.

Right.

So you're saying there's like a relationship there between how much time we spend and how good the solution is.

Exactly.

Yeah.

Okay, cool.

So our mission today in this deep dive is to really explore like some concrete examples of these polynomial time approximation algorithms.

We want to give you like a solid understanding of how we can actually deal with these super hard problems in a practical way.

So are you ready to get into it?

Absolutely.

Let's start with, I guess, a pretty basic problem, the vertex cover problem.

Okay.

So the vertex cover problem.

This is like our material describes it as an NP complete problem where we're trying to minimize something.

Imagine you have a network, like think about train lines connecting different stations, right?

I like that.

Right.

So we want to choose the smallest number of stations, the vertices, such that every single train line, you know, the edge, has at least one of its end stations, like selected.

Right.

And that set of stations that we picked, that's our vertex cover, and we want the smallest one possible.

Exactly.

Yeah.

And the material presents a really elegant and like simple algorithm for this called Aprox vertex cover, and it works like this.

You just keep picking any train line in the network, and then you add both stations at the end of that line to your set of, like, selected stations.

Okay.

And then you remove all the train lines that are connected to those stations, and you keep doing this until all the lines are, like, covered.

Okay.

I'm following.

I'm following.

So this is pretty straightforward, right?

Yeah.

But here's what's really interesting.

So the material, it points out that even though this seems so simple, it guarantees an approximation ratio of two.

So think about that.

Even though finding the absolute fewest stations might be really, really hard,

this little process makes sure that we'll never pick more than twice the optimal number.

Right.

That's pretty amazing, I think, for a problem that's so hard, wouldn't you say?

Yeah.

It's a really strong guarantee.

Yeah.

So what's the, like, the secret sauce?

What makes this two approximation work so well?

Well, the reason is because the set of train lines, you know, the edges that the algorithm picks,

they form what's called a maximal matching.

Maximal matching.

Yeah.

So a matching, it's basically just a set of edges that don't share any vertices in any stations in our example.

Okay.

And it's maximal if you can't add any more edges to it without, like, breaking that rule of them not sharing vertices.

Got it.

Okay.

So why is this maximal matching so important?

Like, how does it connect to this approximation ratio of two?

Okay, so let's think about any maximal matching our algorithm comes up with.

Every single train line in that matching has to have at least one of its stations included in any vertex cover, including the absolute best one.

Right, because every line needs to be covered.

Exactly.

Right.

And since no two lines in our matching share a station, each line is basically demanding at least one unique station in the cover.

Okay.

So the size of our maximal matching is like a lower limit on the size of the optimal vertex cover.

Okay.

I'm starting to see it now.

Yeah.

So our algorithm for each line it picks in this matching, it adds both of the stations to our cover.

Right.

So we're adding at most two stations for each line.

And since the matching size is like a lower bound, our solution can't be more than twice as big as the optimal one.

That's really clever.

Yeah.

It's a neat way to use the structure of the problem to get this guaranteed.

Yeah.

Now, I know you mentioned that this algorithm, it doesn't always find the absolute smallest cover.

Are there like cases where it might pick more stations than absolutely necessary?

Yeah, absolutely.

There are definitely cases where it overshoots.

But the nice thing is, we know it'll never be worse than twice the optimal size.

Right, right.

We have that guarantee.

Okay, cool.

So let's move on to a different NP complete problem.

One that, you know, maybe a lot of people have heard of, it's the traveling salesperson problem, TSP.

Ah, yes, classic TSP.

So this is the scenario where, you know, you have a salesperson, they need to visit a bunch of cities and they want to find the absolute shortest route that visits each city exactly once and brings them back to the starting point.

Right.

A grand tour.

And as the material really emphasizes,

the possibility of getting good approximations for the TSP really depends on this, this key condition,

whether something called the triangle inequality holds for the distances between the cities.

Okay, so triangle inequality.

For those who might not remember from, you know, geometry class or whatever, can you remind us what that means when we're talking about traveling between cities?

Sure.

So imagine you have three cities, let's call them A, B and C.

Okay.

The triangle inequality just says that the direct distance from city A to C will always be less than or equal to the distance of going from A to B and then from B to C.

Okay, so it's basically saying that like taking a detour is never shorter than going straight.

Exactly.

Yeah.

And this is usually true for like geographical distances, right?

But in some more abstract versions of the TSP, it might not always be the case.

Okay, got it.

So what happens if this triangle inequality does hold?

So the material is it talks about this algorithm called APPR X TSP tour.

And it says that this gives us a two approximation for this scenario.

How does that algorithm actually work?

So it's a two part process.

First the algorithm builds what's called a minimum spanning tree or an MST for the network of cities.

Okay.

MST.

Yeah.

And you can think of this MST like as a backbone, right?

It connects all the cities together using the shortest possible total length of roads,

but without creating any cycles, you know, like loops.

Okay, right.

So we've talked about minimum spanning trees before, I think.

So we have this tree that connects all our cities in the shortest way possible.

What's the next step to make our tour?

So the next step is to do what's called a preorder traversal of this MST.

So imagine you're walking through this tree, right?

Okay.

Visit the starting city first.

That's like the root of the tree.

And then you go as deep as you can into one branch and then you come back up and explore another branch and so on.

And as you're doing this, you just write down the order in which you first visit each city.

And that order, that becomes our TSP tour.

So we're like tracing around the outline of this MST.

Exactly.

Okay.

And how does this guarantee that our tour is not like ridiculously longer than the optimal TSP tour?

Like how does this give us that two approximation?

So the key is that the total length of the MST itself is like a lower bound on the length of any possible TSP tour.

Because if you take any valid TSP tour and remove just one edge, what you're left with is still a path connecting all the cities.

And that path is a spanning tree, right?

But since the MST is by definition the shortest possible spanning tree, the optimal TSP tour has to be at least as long as the MST.

Okay.

That makes sense.

And how does the pre -order walk thing tie into this?

Well, in our pre -order walk, we travel along each edge of the MST at most twice.

One's going down and one's coming back up.

So the total length of our tour is at most twice the length of the MST.

And since the MST length is a lower bound,

our tour is at most twice as long as the optimal tour.

So there's our two approximation.

Wow.

That's really neat how that connects those two ideas from graph theory.

But our material also points out this, like, kind of a bummer of a result, you know?

When the triangle inequality doesn't hold, what's the deal with that?

Yeah, this is a crucial point.

So basically, Demshiro says if the triangle inequality doesn't hold, then no matter what constant approximation ratio you want, like, say, a guarantee that your solution is never more than three times the optimal, there's no algorithm that can achieve that in polynomial time unless P equals NP.

Oh, wow.

So it's a strong indication that without the triangle inequality, getting any kind of decent approximation for TSP is probably just not going to happen in a reasonable amount of time.

So that triangle inequality thing, it's really make or break for TSP.

Yeah.

It's really fundamental for making the problem even somewhat approachable.

Huh.

OK.

All right.

Well, let's move on to another NP -complete problem.

This one is the set covering problem.

What's the idea behind this one?

So the set covering problem, it comes up when you have, like, a bunch of elements, let's call it a universe of elements, and you're given a collection of sets, and each set contains some of these elements.

Right.

The goal is to pick the smallest number of these sets so that together, they contain all the elements in the universe.

OK.

I think I'm following.

Can you give me an example, like a real -world scenario?

Sure.

Imagine you're putting together a project team, right?

OK.

And you need a certain set of skills covered.

So you have a bunch of people, and each person has their own unique set of skills.

The set covering problem is basically asking you to find the smallest group of people you need to hire so that you have all the skills covered.

OK.

That makes it way more clear.

So for this problem, our material talks about, like, a greedy approach.

It's called, creatively, the greedy set cover algorithm.

Right.

So how does this greedy strategy work?

It's pretty intuitive, actually.

You start with no skills covered and an empty team.

Then in each step, you look at all the available people, and you choose the one who brings the most new skills to the table, you know, skills that aren't already covered by the people you've picked.

Yeah.

You add this person to your team, and then you just repeat the process until you have all the necessary skills covered.

OK.

So at each step, we're being greedy and grabbing the person who gives us the most bang for buck at that moment.

Exactly.

So what kind of approximation ratio do we get with this?

Is it, like, a constant factor, like we saw with vertex cover and TSP?

Well, no.

Interestingly, it's not a constant factor this time.

The material tells us that if the best possible team size, the optimal one, is C dollar and the total number of skills we need is $6,

then this greedy algorithm will give us a team taller that's at most CL and X plus LN in size.

OK.

So the approximation ratio is on the order of LNXDN, and then LNXDL there, that's the natural logarithm of the number of elements in our universe.

So it's not as good as a constant factor, but it's still polynomial time, right?

And a logarithmic factor, maybe that's not too bad in a lot of real world situations, especially if the number of skills or elements that we need to cover isn't super huge.

Yeah, that's right.

I mean, the approximation might get a bit worse as the problem gets bigger, but this greedy approach is still super practical because it's simple and fast.

Yeah.

And we have a guarantee on how far from optimal it can be.

Cool.

OK.

So now our material switches gears a little bit.

It talks about some more advanced techniques that we can use to design these approximation algorithms,

things like randomization and linear programming.

Let's start with randomization.

How can randomness chance help us find good approximate solutions?

Yeah, it's pretty cool, actually.

Randomization can be really powerful.

So the material gives us example with a simple randomized algorithm for the MX3CNF satisfiability problem.

OK.

MX3CNF.

Yeah, it's a mouthful.

But basically in this problem, we have a Boolean formula, you know, with trues and falses, and we want to find an assignment of true or false values to the variables so that we satisfy as many clauses in the formulas as possible.

And the randomized algorithm is super simple.

For each variable, you just flip a coin.

And if it's heads, you set it to true, if it's tails, you set it to false.

So we're just, like, randomly assigning values.

Yeah, pretty much.

That seems almost too simple.

What kind of results can we expect from that?

Well, surprisingly, this basic approach actually gives you an expected approximation ratio of 87.

So on average, this random assignment will satisfy at least 78 of the maximum number of clauses that you could possibly satisfy.

OK.

So randomness can actually give us, like, a decent guarantee.

Yeah.

It's a good illustration of how probabilistic methods could be really useful.

OK, that's pretty neat.

So now let's talk about linear programming.

I remember those from, like, optimization theory, I think.

Right.

How do they fit into this world of approximation algorithms?

OK, so linear programming, LP, it's a way to solve optimization problems where all the relationships between the variables are linear.

Right.

And a lot of NP -complete problems, you can actually write them as integer linear programs, or ILPs.

OK.

So in these ILPs, the variables can only be integers, like 0 or 1, to represent yes or no decisions.

Yeah.

But the problem is, solving these ILPs, in general, it's just as hard as solving the original NP -complete problem.

So how do we use linear programming to help us?

The trick is to relax the integer constraints.

So instead of only allowing integers, we let the variables take on any value between 0 and 1.

So now it becomes a regular linear program, which we can solve quickly in polynomial time.

And the optimal solution to this relaxed LP gives us a lower bound on the optimal solution to the original problem with integers.

OK, so we get a solution where our decision variables can be fractions.

Right.

But how do we turn that back into, like, a real solution where we have to make yes or no decisions?

That's where rounding comes in.

So the material gives us an example of the weighted vertex cover problem.

It's like the regular vertex cover problem, but now each vertex has a weight, a cost.

Right.

And we want to find a vertex cover with the smallest total weight.

So after we solve the linear programming relaxation, we get these fractional values for each vertex.

And then a common rounding strategy is to just say, hey, if the fractional value for a vertex is at least 12, we'll include that vertex in our cover.

Makes sense.

And this algorithm, they call it APProcXMNWHTVC.

OK.

So what kind of approximation ratio do we get from this linear programming and rounding business?

So it turns out this also gives us a two approximation ratio.

And the reason is, basically, the weight of our cover, the one we get from rounding, it can be shown to be at most twice the optimal solution of the linear program, which, remember, was a lower bound on the optimal weight of the real vertex cover.

Right, right.

OK, so linear programming, it gives us another tool to tackle these hard problems.

So we get a lower bound on the optimal solution.

And then we use rounding to turn it into a real solution with a guaranteed approximation ratio.

Exactly, yeah.

It's a pretty versatile technique.

OK, cool.

So the last thing the material talks about is this really sophisticated concept called a fully polynomial time approximation scheme.

Right, an FPTAS.

Yeah, FPTAS.

So catchy.

OK, this is for the subset sum problem, right?

So can you remind me what that problem is?

Yeah, so the subset sum problem is you're given a set of numbers and a target sum.

And you want to know, is there a subset of those numbers that adds up exactly to the target?

OK, yeah.

And this is another NP complete problem.

Now, an FPTAS, it's like a super powered approximation algorithm.

So it takes the regular input to the problem, but it also takes an extra parameter, let's call it epsilon, which is a small positive number.

And you can use this epsilon to control how accurate you want your approximation to be.

OK.

So the cool thing about an FPTAS is that for any fixed epsilon, the algorithm runs in polynomial time.

But it's polynomial in both the size of the input, the number of numbers in our set, and in one epsilon.

OK.

And it also guarantees an approximation ratio of $1 plus epsilon.

So by making epsilon smaller, we can get an approximation that's really, really close to the optimal solution.

And the runtime is still polynomial as long as epsilon isn't super tiny.

Exactly, yeah.

That's pretty awesome.

Yeah, it's very powerful.

So the material, it briefly mentions an exact algorithm for subset sum called exact subset sum.

But that algorithm, it can take exponential time.

Right, so not very practical.

Yeah.

So the core idea of the FTPAS, this one is called a proxet subset sum, is to trim the list of partial sums that we generate as we go through the numbers in the set.

Hmm.

Trimming.

What does that mean in this context?

So at each step, we're building this list of all the possible sums we can make from the numbers we've looked at so far.

OK.

And we look for sums that are really close to each other in value.

So if we have two sums, let's say, and less than or equal to 0 is less than or equal to theirs times 1 plus delta,

where delta is a trimming parameter based on our epsilon,

then we can just throw away 0s.

OK.

And the reasoning is that $ is already a good enough approximation for any solution we could have gotten using 0a.

So by trimming these, like, redundant sums, we keep the total number of sums we need to remember small enough to make the algorithm run in polynomial time, but we still get a good approximation in the end.

So it's all about finding that sweet spot between exploring all the possibilities and keeping things efficient by getting rid of sums that are basically the same, right?

Yeah.

That's the idea.

OK, wow.

That's pretty sophisticated.

It is.

And it shows us that for some of these NP -complete problems, even though we probably can't find an exact solution quickly,

we can still get really good approximate solutions with algorithms that run in a reasonable amount of time.

Yeah, that's really cool.

Well, this has been a really awesome deep dive.

I mean, it's amazing to see all these different strategies we can use when we're dealing with problems that are just too hard to solve perfectly.

Yeah, definitely.

We've seen these simple but effective greedy approaches, algorithms that use special properties of the problem like the triangle inequality and these more advanced techniques like randomization and linear programming.

And we even touched on this really powerful FPTAS concept.

Yeah, and it's not just the algorithms themselves.

It's like the whole way of thinking about these hard problems.

We don't always need the absolute best answer, right?

Sometimes good enough is good enough, especially if we can find that good enough solution quickly.

Yeah, it's about being practical.

Exactly.

So just to recap some of the specific algorithms we looked at, we had APROX vertex cover, which gives us a two approximation, APROX TSP tour, also a two approximation, but only if the triangle inequality holds.

We had greedy set cover, which gives us an LNX approximation and that random algorithm for max3CNF with the expected 87 ratio.

And then we talked about APROXMAN weight TVC using linear programming with the two approximation.

And finally, that FPTAS APROX subset sum with a $1 plus epsilon approximation.

And as you pointed out, it's great to see the variety of techniques, right?

We have these greedy strategies, algorithms that exploit specific properties of the problem, probabilistic methods, linear programming, relaxations, dynamic programming, and trimming.

So a whole toolkit for dealing with NP complete problems.

Yeah, absolutely.

So as you go about your day and you come across these really complex problems, remember that you don't always need the perfect answer.

Sometimes a good enough answer found in a reasonable amount of time is perfectly fine.

So think about other real world challenges that seem really hard.

Could you use some of the ideas from approximation algorithms to find practical solutions?

Yeah, it's a great question to keep in mind.

I mean, there's often this middle ground between the ideal solution and what we can actually compute and approximation algorithms.

They give us a way to find those good enough solutions.

And that's what makes them so powerful.

So thanks for joining me on this deep dive.

And until next time, keep those algorithmic gears turning.

Always.

All right.

See ya.

See ya.