Thursday, August 9 2018
14:00 - 15:00

#### Graph partitioning refers to a class of algorithmic problems thatask for a partition of an input graph G into two or more parts, whileoptimizing an objective function that measures the quality of thepartition. One natural criteria that is of both theoretical and practicalsignificance is that the cuts are 'sparse': they split the graph intobalanced parts with very few interactions across the parts. Although theseproblems are usually NP-Hard to approximate (up to large factors) in thegeneral case, input graphs in practice often have some kind of structure that could help one find better sparse cuts more efficiently. This presentsus with the natural question of designing algorithms that give betterguarantees or are more efficient for such input instances.In this talk, we will mainly focus on how the Sparsest Cut problem can besolved efficiently on a class of graphs called low threshold-rank graphs.The Sparsest Cut objective measures the sparsity of a cut in terms of edgesgoing across the cut, normalized by the size of the partition. While thebest known approximation guarantee for this problem is $O(\sqrt{\log n})$ ingeneral, we show that one can do much better on graphs which already have a'clustered' structure, using an efficient and intuitive algorithm. Ouralgorithm also furnishes a generalization of a geometric theorem ofGoemans on embedding finite metric spaces into $\ell_1$.In the latter part of the talk, we will briefly look at a naturalsemi-random model of generating clustered input graphs where a betterobjective is to consider the number of boundary vertices on the cut, asopposed to edges across it. We will see an outline of how to exactlyrecover a sparse vertex-cut in this setting using Semidefinite Programming.(Based on joint works with Amit Deshpande, Prahladh Harsha, Anand Louis andYuval Rabani).

Download as iCalendar

Done