Filtering and the Primal-Dual Method – Part 1


December 21, 2012


Two LP-based methods were covered. Filtering the optimal LP solution was illustrated to design a constant factor approximation for the metric uncapacitated facility location problem. The primal-dual method was illustrated by designing a 2-approximation algorithm for the generalized Steiner forest problem.


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.