Algorithms and Complexity Seminar

Monday, February 25, 2008, 4:00-5:15pm in 32-G575.

Approximate Hypergraph Partitioning and Applications

Arie Matsliah (Technion)

I will present an algorithm that given eps>0 and a graph G on n vertices outputs an eps-regular partition of G in O(n) time.

Unlike the previous approaches for this problem that "reproved" Szemerdi's regularity lemma algorithmically and therefore guaranteed to find partitions of tower-size only, our algorithm will find a small regular partition if one exists.

The main tool that we develop for the above task is an algorithm for finding approximate partitions of hypergraphs, which generalizes the algorithm of Goldreich-Goldwasser-Ron for finding approximate partitions of graphs.

Joint work with Eldar Fischer and Asaf Shapira

Paper can be found at: http://www.cs.technion.ac.il/~ariem/papers/ahp.pdf

Host: Ronitt Rubinfeld

(The Algorithms and Complexity Seminar series talks are usually held Thursdays 4:00-5:15pm in 32-G575.)