Sublinear Graph Approximation Algorithms
Jan 26, 2011
ABSTRACT: I will survey results on approximation algorithms for the SIZE of the maximum matching, minimum vertex cover, and other packing and covering problems. These algorithms often run in time sublinear in the graph size. In particular, I will focus on the class of CONSTANT-TIME algorithms, that is, algorithms that run in time that is a function of only the average degree and an approximation quality parameter epsilon.

Highlights include:

* a technique for transforming classical approximation algorithms into constant-time algorithms,

* the first constant-time algorithm for approximating the maximum matching size up to an additive epsilon*n, where n is the number of vertices,

* a simple proof of the theorem of Benjamini, Schramm, and Shapira that every minor-closed property of sparse graphs is testable in constant time.