Speaker Claire Mathieu
Affiliation Brown University
Host Yuval Peres
Date recorded 23 August 2010
How can we efficiently aggregate rankings, cut a graph into two parts with many edges between them, pack items into bins, cluster items using pairwise similarity information, route vehicles in the Euclidean plane, or construct a Steiner tree in a planar graph? All these examples of optimization problems are NP-hard, yet, under some mild assumptions, they all have near-optimal solutions that can be computed in (high) polynomial time. I will present a few algorithmic techniques and their application to the above problems.
©2010 Microsoft Corporation. All rights reserved.