Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
Metric Rounding of LP Relaxations

Speaker  R. Ravi

Affiliation  Tepper School of Business

Host  Ravi Kannan

Duration  01:40:32

Date recorded  21 December 2012

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.

©2012 Microsoft Corporation. All rights reserved.
> Metric Rounding of LP Relaxations