Linear Programs and Deterministic Rounding

Date

December 20, 2012

Overview

Linear and integer programs were introduced and simple deterministic rounding was demonstrated for the vertex cover problem (2-approximation). The homework assigned was to design a deterministic rounding algorithm for the prize-collecting vertex cover problem.

Speakers

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.

‚Äč