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

[Dawn Ellis]

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/20140206/872f3058/attachment-0001.htm