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.

Oded's comments

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). Parnas 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 Constant-Time Approximation Algorithms via Local Improvements (by Nguyen and Onak), An 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.


Back to list of Oded's choices.