Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
How to Approximate it? Introduction and Greedy Algorithms - Part 1

Speaker  R. Ravi

Affiliation  Tepper School of Business

Host  Ravi Kannan

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