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.