Sublinear-Time Approximation Algorithms

Prof. Artur Czumaj
UK, Centre for Discrete Mathematics and its Applications (DIMAP), University of Warwick Sublinear-time Approximation Algorithms
We will survey some of the recent algorithmic approaches to design sublinear-time algorithms to determine cluster structure of graphs.
As a concrete example, we will show how to test in O*(n^{1/2})-time whether a graph with n nodes can be partitioned into no more than k clusters such that the outer-conductance of each cluster is at least phi_out and the inner-conductance of the induced subgraph on each cluster is at least phi_in, for a large spectrum of parameters k, phi_out and phi_in.