Approximation Schemes for Optimization

Speaker  Claire Mathieu

Host  Yuval Peres

Affiliation  Brown University

Duration  01:00:58

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.
> Approximation Schemes for Optimization