| Title | : | Graph Partitioning on Low Threshold-Rank and Semi-Random Graphs |
| Speaker | : | Rakesh Venkat (Hebrew University of Jerusalem, Israel) |
| Details | : | Thu, 28 Jun, 2018 11:00 AM @ A M Turing Hall |
| Abstract: | : | Graph partitioning refers to a class of algorithmic problems that ask for a partition of an input graph $G$ into two or more parts, while optimizing an objective function that measures the quality of the partition. One natural criteria that is of both theoretical and practical significance is that the cuts are sparse: they split the graph into balanced parts with very few interactions across the parts. Although these problems are usually NP-Hard to approximate (up to large factors) in the general case, input graphs in practice often have some kind of structure that could help one find better sparse cuts more efficiently. This presents us with the natural question of designing algorithms that give better guarantees or are more efficient for such input instances. In this talk, we will mainly focus on how the Sparsest Cut problem can be solved efficiently on a class of graphs called low threshold-rank graphs. The Sparsest Cut objective measures the sparsity of a cut in terms of edges going across the cut, normalized by the size of the partition. While the best known approximation guarantee for this problem is $O(sqrt{log n})$ in general, we show that one can do much better on graphs which already have a clustered structure, using an efficient and intuitive algorithm. Our algorithm also furnishes a generalization of a geometric theorem of Goemans on embedding finite metric spaces into $ell_1$. In the latter part of the talk, we will briefly look at a natural semi-random model of generating clustered input graphs where a better objective is to consider the number of boundary vertices on the cut, as opposed to edges across it. We will see an outline of how to exactly recover a sparse vertex-cut for a wide range of the model parameters using Semidefinite Programming. (Based on joint works with Amit Deshpande, Prahladh Harsha, Anand Louis and Yuval Rabani). Speaker Bio: The speaker is a postdoctoral fellow at the Hebrew University of Jerusalem, Israel. Prior to this, he obtained his PhD from the Tata Institute of Fundamental Research, Mumbai. His research interests are in Approximation Algorithms, Spectral Graph theory, and Hardness of Approximation. |
