[Colloquium] [TTIC Talks] REMINDER: Talks at TTIC: Anand Louis, Georgia Institute of Technology

[Madhur Tulsiani]

The talk starts in 10 minutes...

Madhur


On Wed, Feb 12, 2014 at 7:57 AM, Dawn Ellis <dellis at ttic.edu> wrote:

> When:     Thursday, February 13th at 11am
>
> Where:    TTIC, 6045 S Kenwood Avenue, 5th Floor, Room #526
>
> Speaker:  Anand Louis,  Georgia Institute of Technology
>
> Title :
> Spectral and Approximation Algorithms for Graph Partitioning Problems
>
> Abstract:
>
> Cheeger's fundamental inequality says that any graph has a vertex subset
> whose expansion (a.k.a. conductance) is bounded by twice the square root of
> the second smallest eigenvalue of the normalized Laplacian of the graph.
> This inequality and its algorithmic proof have a myriad of applications.
>
> I will present an almost optimal generalization of Cheeger's inequality :
> Given a parameter k, there exists a k/2-partition of the vertex set of the
> graph such that the expansion of each piece is bounded by O(\sqrt{\lambda_k
> log k}), where \lambda_k is the kth smallest eigenvalue of the normalized
> of the graph. The proof is via a simple randomized O(kn) time algorithm to
> compute the partition.
>
> The underlying algorithmic problem, namely finding a k-partition such that
> the maximum expansion is minimized, besides extending sparsest-cut to more
> than one subset, appears to be a natural clustering problem in its own
> right. I will also present a O(\sqrt{log n log k}) approximation algorithm
> for this problem; and some better approximations for some special families
> of graphs.
>
>
> Based on joint work with Konstantin Makarychev, Prasad Raghavendra, Prasad
> Tetali and Santosh Vempala.
>
>
> Host: Madhur Tulsiani, madhurt at ttic.edu
>
> --
> *Dawn Ellis*
> Administrative Coordinator,
> Bookkeeper
> 773-834-1757
> dellis at ttic.edu
>
> TTIC
> 6045 S. Kenwood Ave.
> Chicago, IL. 60637
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20140213/61180e05/attachment-0001.htm