Calendar Site

Loading Events

« All Events

  • This event has passed.

Graph Partitioning for Low Threshold-Rank and Semi-Random Instances

August 7, 2018 @ 12:00 pm - 1:00 pm

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$.Discipline/Coordinating Entity: Computer Science and Engineering


August 7, 2018
12:00 pm - 1:00 pm
Event Category: