Talks & Seminars
Expander flows and a sqrt(log n) approximation for sparsest cuts
Umesh Vazirani,
Date & Time: January 5, 2004 15:30
Venue: Seminar Hall
Cutting a graph into two roughly equal pieces while minimizing the number of edges cut is a natural primitive in algorithm design, especially in divide-and-conquer approaches. We give new approximation algorithms for the most well-studied problems in this class, improving upon the celebrated Leighton-Rao O(log n) approximation algorithm. The algorithm is based upon a well-known semidefinite relaxation that uses triangle inequalityconstraints. Underlying the algorithm is a new result about graph embeddings: for every constant degree graph (with expansion alpha), it is possible to embed an n-node expander in it with dilation and congestion sqrt(log n)/alpha
Speaker Profile:
List of Talks


Faculty CSE IT
Forgot Password
    [+] Sitemap     Feedback