Algorithms and Complexity Seminar
Constant-Time Approximation Algorithms via Local Improvements
Krzysztof Onak (MIT)
We present a technique for transforming classical approximation algorithms into
constant-time algorithms that approximate the size of the optimal solution. Our
technique is applicable to a certain subclass of algorithms that compute
a solution in a constant number of phases. The technique is based on greedily
considering local improvements in random order.
The problems amenable to our technique include Vertex Cover, Maximum Matching,
Maximum Weight Matching, Set Cover, and Minimum Dominating Set. For example, for
Maximum Matching, we give the first constant-time algorithm that for the class
of graphs of degree bounded by d, computes the maximum matching size to within
epsilon * n, for any epsilon > 0, where n is the number of nodes in the graph.
The running time of the algorithm is independent of n, and only depends on d and
Joint work with Huy N. Nguyen (MIT)