Approximation Algorithms Part I

Por: Coursera . en: , ,

  • Vertex cover and Linear Programming
    • We introduce the course topic by a typical example of a basic problem, called Vertex Cover, for which we will design and analyze a state-of-the-art approximation algorithm using two basic techniques, called Linear Programming Relaxation and Rounding. It is a simple, elementary application of powerful techniques.
  • Knapsack and Rounding
    • This module shows the power of rounding by using it to design a near-optimal solution to another basic problem: the Knapsack problem.
  • Bin Packing, Linear Programming and Rounding
    • This module shows the sophistication of rounding by using a clever variant for another basic problem: bin packing. (This is a more advanced module.)
  • Set Cover and Randomized Rounding
    • This module introduces a simple and powerful variant of rounding, based on probability: randomized rounding. Its power is applied to another basic problem, the Set Cover problem.
  • Multiway Cut and Randomized Rounding
    • This module deepens the understanding of randomized rounding by developing a sophisticated variant and applying it to another basic problem, the Multiway Cut problem. (This is a more advanced module.)

Plataforma