How to Approximate it? Introduction and Greedy Algorithms - Part 1

Speaker  R. Ravi

Host  Ravi Kannan

Affiliation  Tepper School of Business

Duration  01:36:20

Date recorded  17 December 2012

The lecture starts with an outline of the topics proposed to be covered, followed by an introduction to greedy algorithms illustrated using the set cover problem (logarithmic ratio approximation). The homework assigned was to analyze the greedy method applied to Uncapacitated Facility Location, and the Generalized Steiner Forest problems.

©2012 Microsoft Corporation. All rights reserved.
> How to Approximate it? Introduction and Greedy Algorithms - Part 1