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

Channel:
Microsoft Research
Subscribers:
344,000
Published on ● Video Link: https://www.youtube.com/watch?v=1XPKOJgsYJM


Duration: 1:36:43
3,006 views
48

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.



Other Videos By Microsoft Research


2016-08-11AstroInformatics 2012: Day 1 Session 4
2016-08-11New Directions in Networked Systems Design - Session 2
2016-08-11Towards Provable Bounds for Machine Learning - Lecture 3
2016-08-11Linear Programs and Deterministic Rounding
2016-08-11Towards Provable Bounds for Machine Learning - Lecture 1
2016-08-11Filtering and the Primal-Dual Method - Part 2
2016-08-11Differential Privacy - Lecture 2
2016-08-11Towards Provable Bounds for Machine Learning - Lecture 2 Part 1
2016-08-11Local Search
2016-08-11Differential Privacy - Lecture 4
2016-08-11How to Approximate it? Introduction and Greedy Algorithms - Part 1
2016-08-11Differential Privacy - Lecture 5
2016-08-11Filtering and the Primal-Dual Method - Part 1
2016-08-11Differential Privacy - Lecture 3
2016-08-11Big Data Processing on the Cheap
2016-08-11Differential Privacy - Lecture 1
2016-08-11Towards Provable Bounds for Machine Learning - Lecture 2 Part 2
2016-08-11Handling Big Data for the Environmental Informatics; Real-Time Environmental Observation
2016-08-11Machine Learning Course - Lecture 4
2016-08-11From Algorithms to Auctions
2016-08-11A Noise-Robust Speech Recognition Method


Tags:
microsoft research