Optimization: Beyond Heuristics and Dealing with Uncertainty: Karthekeyan Chandrasekaran, Harvard (CS Colloquium)

11:00 am on Monday, February 10, 2014
12:15 pm on Monday, February 10, 2014
MCS 148
Abstract Optimization problems are ubiquitous in contemporary science and engineering. The principal barriers to solving several optimization problems are input uncertainty and large solution space. In this talk, I will address two algorithmic approaches to overcome these difficulties. First, I will give provable guarantees for a well-known heuristic, namely the cutting plane method, to find min-cost perfect matchings. Second, I will present new tools to study probabilistic instances of integer programs.