May 7, Tuesday
12:00 – 13:00
On Sublinear Algorithms for Approximating Graph Parameters
Computer Science seminar
Lecturer : Dana Ron
Affiliation : Department of Electrical Engineering - Systems, Tel-Aviv University
Location : 202/37
Host : Dr. Aryeh Kontorovich
When we refer to efficient algorithms, we usually mean
polynomial-time algorithms. In particular this is true for graph
algorithms, which are considered efficient if they run in time
polynomial in the number of vertices and edges of the graph.
However, in some cases we may seek even more efficient algorithms
whose running time is sublinear in the size of the input graph.
Such algorithms do not even read the whole input graph, but rather
sample random parts of the graph and compute approximations of various
parameters of interest.
In this talk I will survey various such algorithms, where the
parameters I will discuss are:
(1) The average degree the number of small stars
(2) The weight of a minimum spanning tree
(3) The size of a minimum vertex cover and a maximum matching
(4) The number of edges that should be added/removed in order to
obtain various properties