Metric Rounding of LP Relaxations


December 22, 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.


R. Ravi

Professor R. Ravi is Carnegie Bosch Professor of Operations Research and Computer Science at Carnegie Mellon University. Ravi received his bachelor’s from IIT, Madras, and Master’s and doctoral degrees from Brown University, all in Computer Science. He has been at the Tepper School of Business since 1995 where he served as the Associate Dean for Intellectual Strategy from 2005-2008. Ravi’s main research interests are in Combinatorial Optimization (particularly in Approximation Algorithms), Computational Molecular Biology and Electronic Commerce. He currently serves on the editorial boards of Management Science and the ACM Transactions on Algorithms.