## Carrying Over Algorithms - Intro to Theoretical Computer Science

• 0:00 - 0:07
So now we have factor two approximation algorithms for Alice, who is, of course, very happy about this.
• 0:07 - 0:11
And we've also found a factor two approximation algorithm for the problem that Dave was working on.
• 0:11 - 0:17
So Dave is, of course, equally happy. Now, the question: Since Alice and Dave apparently are working on problems
• 0:17 - 0:20
that can be approximated very well, what about Bob and Carol?
• 0:20 - 0:26
And as you remember, the problems that Bob and Carol are working on are closely related to the one that Alice was working on.
• 0:26 - 0:33
So, Alice was working on Vertex Cover, Bob was working, as you'll remember, on Clique, and Carol was working on Independent Set.
• 0:33 - 0:38
So we already know that we have a factor two approximation algorithm for Vertex Cover.
• 0:38 - 0:42
And from the previous units, you also know how closely Vertex Cover is related to,
• 0:42 - 0:48
well, first of all, Independent Set, but also Clique. Given the close relation, we take this algorithm here and simply
• 0:48 - 0:52
carry over our insight for Vertex Cover to Clique and Independent Set.
• 0:52 - 0:56
So the question now is, given this factor two approximation for Vertex Cover, and given the close relation
• 0:56 - 1:01
of Vertex Cover to Clique and Independent Set, do we now also know that there's a factor two approximation for
• 1:01 - 1:06
Clique and Independent Set? And I'm just writing Independent Set as IS here, to save some space.
Title:
Carrying Over Algorithms - Intro to Theoretical Computer Science
Video Language:
English
Team:
Udacity
Project:
CS313 - Theoretical Computer Science
Duration:
01:07
 Udacity Robot edited English subtitles for cs313 unit53 01 q Carrying Over Algorithms sp1 added a translation

# English subtitles

## Revisions Compare revisions

• API
Udacity Robot
• sp1