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.
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.