Sublinear Graph Approximation Algorithms
by Krzysztof Onak, based on joint works
with Noga Alon, Avinatan Hassidim, Jonathan A. Kelner,
Philip N. Klein, and Huy N. Nguyen.
A natural setting in which sublinear time algorithms
may be useful is in approximating the value of various
graph theoretic quantities, especially when these quantities
are hard to determine (e.g., minVC).
and Ron (2007)
and Marko and Ron (2007) focused
on maximal matching and minVC, while observing a correspondance
between constant-time approximation algorithms for the size of
the maximal independent set and distributed algorithms that
find such sets. The current works continue this line of research,
while extending the study to many other problems (e.g., manimum
matching, minimum dominating sets, etc)
and introducing new techniques and improved results.
For details, see
Approximation Algorithms via Local Improvements (by Nguyen and Onak),
Improved Constant-Time Approximation Algorithm for Maximum Matchings
(by Yoshida, Yamamoto and Ito), and forthcoming papers.
The original abstract
Can the size of a solution to a graph problem be computed faster than
the solution itself? I will show that the answer to this question is
positive in many cases.
For example, I will present an approximation algorithm that for the
class of graphs with degree bounded by d, computes the maximum
matching size to within $\epsilon * n$ in time that only depends
on $d$ and $\epsilon$.
I will give an overview of all known results, including some work
still in progress.
list of Oded's choices.