WEBVTT
00:00:00.167 --> 00:00:06.699
So now we have factor two approximation algorithms for Alice, who is, of course, very happy about this.
00:00:06.700 --> 00:00:11.466
And we've also found a factor two approximation algorithm for the problem that Dave was working on.
00:00:11.467 --> 00:00:16.566
So Dave is, of course, equally happy. Now, the question: Since Alice and Dave apparently are working on problems
00:00:16.567 --> 00:00:20.232
that can be approximated very well, what about Bob and Carol?
00:00:20.233 --> 00:00:26.466
And as you remember, the problems that Bob and Carol are working on are closely related to the one that Alice was working on.
00:00:26.467 --> 00:00:33.299
So, Alice was working on Vertex Cover, Bob was working, as you'll remember, on Clique, and Carol was working on Independent Set.
00:00:33.300 --> 00:00:37.566
So we already know that we have a factor two approximation algorithm for Vertex Cover.
00:00:37.567 --> 00:00:41.932
And from the previous units, you also know how closely Vertex Cover is related to,
00:00:41.933 --> 00:00:48.266
well, first of all, Independent Set, but also Clique. Given the close relation, we take this algorithm here and simply
00:00:48.267 --> 00:00:51.666
carry over our insight for Vertex Cover to Clique and Independent Set.
00:00:51.667 --> 00:00:56.399
So the question now is, given this factor two approximation for Vertex Cover, and given the close relation
00:00:56.400 --> 00:01:01.366
of Vertex Cover to Clique and Independent Set, do we now also know that there's a factor two approximation for
00:01:01.367 --> 00:01:06.300
Clique and Independent Set? And I'm just writing Independent Set as IS here, to save some space.