Iterative Methods in Combinatorial Optimization
R. Ravi
Tepper School of Business
Carnegie Mellon University
Tuesday, May 6, 2014
4:15 - 5:15 PM
Huang 305
Abstract:
In this talk, I will describe a simple iterative method for
proving a variety of results in combinatorial optimization. It
is inspired by Jain's iterative rounding method for designing
approximation algorithms for survivable network design
problems, and augmented with a relaxation idea in the work of
Lau, Naor, Salvatipour and Singh in their work on designing an
approximation algorithm for its degree bounded version. Its
application was further refined in recent work of Bansal,
Khandekar and Nagarajan on degree-bounded directed network
design.
In this talk, I will describe its application to showing the
integrality of Edmond's characterization of the spanning tree
polyhedron and then extend the argument to show a simpler proof
of the Lau-Singh approximation algorithm for its degree
constrained version. I will conclude by showing how Jain's
original proof can be much simplified by the new perspective,
by unifying its treatment with that for the STSP problem.
This talk describes work of all the above authors interpreted
in collaboration with Lau, Nagarajan and Singh.
Dr. R. Ravi is the Andris A. Zoltners Professor of Business and Professor of Operations Research and Computer Science at Carnegie Mellon University. Ravi received his bachelor's degree 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, and Chair of the Future Educational Delivery Committee that launched the online Tepper MBA in 2013. Ravi's main research interests are in algorithms for combinatorial optimization, and their applications in the intersection of business and technology. Ravi is interested in networks and their effects in business, a subject on which he introduced a new MBA class. He is also interested in customer-centric marketing and how to accomplish this using optimization methods on large data sets, on which he co-developed another new MBA class.
On the academic side, Ravi's research has been continually supported by the U.S. National Science Foundation since 1995; In this period, he has supervised a dozen doctoral theses and developed over half a dozen new graduate classes. He currently serves on the editorial board of the ACM Transactions on Algorithms, as well as area editor for Operations Research in charge of the discrete optimization area.
Operations Research Colloquia: http://or.stanford.edu/oras_seminars.html