The Local Search method was illustrated using three problems: Maximum cut (2-approximation), Maximum leaf spanning trees (10-approximation) and the metric k-median problem (3-approximation).
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.