Metric Rounding of LP Relaxations

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


Category:
Let's Play
Duration: 1:40:55
678 views
14

LP relaxations interpreted as metrics (or distance functions in graphs) are useful in designing approximation algorithms for cut problems. This was illustrated by designing an exact algorithm for minimum s-t cut, a 2-approximation for multiway cut in graphs, a 2-approximation for the multicut problem in trees and finally a logarithmic approximation for the multicut problem in general graphs.



Other Videos By Microsoft Research


2016-08-15Retrieval Models for Collaborative Question and Answer Archives
2016-08-15Faceted Search and PivotViewer / HPC and Azure Cloud Computing
2016-08-15Identity-Based Deterministic Signature Scheme Without Forking-Lemma
2016-08-15Towards Provable Bounds for Machine Learning - Lecture 4
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


Tags:
microsoft research