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

Starts:
11:00 am on Monday, February 10, 2014
Ends:
12:15 pm on Monday, February 10, 2014
Location:
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.