Return to Video

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