Metric Rounding of LP Relaxations

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.
  • SpeakerR. Ravi
  • HostRavi Kannan
  • AffiliationTepper School of Business
  • Duration01:40:32
  • Date recorded21 December 2012