Speaker R. Ravi
Affiliation Tepper School of Business
Host Ravi Kannan
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.