Linear Programs and Deterministic Rounding

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


Duration: 1:32:30
1,896 views
29

Linear and integer programs were introduced and simple deterministic rounding was demonstrated for the vertex cover problem (2-approximation). The homework assigned was to design a deterministic rounding algorithm for the prize-collecting vertex cover problem.



Other Videos By Microsoft Research


2016-08-15Functional Programming in the Wild
2016-08-15Intersection Workshop - Towards a perceptually parameterized BTF-material space
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


Tags:
microsoft research