Filtering and the Primal-Dual Method - Part 2

Channel:
Microsoft Research
Subscribers:
344,000
Published on ● Video Link: https://www.youtube.com/watch?v=8jS-dI8WUOE


Duration: 1:38:31
1,065 views
8

Two LP-based methods were covered. Filtering the optimal LP solution was illustrated to design a constant factor approximation for the metric uncapacitated facility location problem. The primal-dual method was illustrated by designing a 2-approximation algorithm for the generalized Steiner forest problem.



Other Videos By Microsoft Research


2016-08-15FestSchrift Session 3: Founding Microsoft Research
2016-08-15Capture of dynamic scene using multiple cameras provides rich spatial-temporal information
2016-08-15Social Graphs, Urban Analytics, and Smartphone Privacy
2016-08-12Tap into smart search with Bing APIs from Microsoft Cognitive Services
2016-08-11Metric Rounding of LP Relaxations
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


Tags:
microsoft research