Approximation Schemes for Optimization

Опубликовано 17 августа 2016, 21:57

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.