Breaking the Multicommodity Flow Barrier for ?log(n)-Approximations to Sparsest Cut

Channel:
Microsoft Research
Subscribers:
344,000
Published on ● Video Link: https://www.youtube.com/watch?v=gucgrIjFh5w


Duration: 1:02:29
598 views
6

We present an algorithm for the sparsest cut problem that simultaneously achieves the better approximation factor of SDP/multicommodity-flow based algorithms and the subquadratic running time of single-commodity flow based algorithms. The idea is that we can turn Arora, Rao, and Vazirani's matching-chaining argument into an algorithm for finding good augmenting paths in a multicommodity flow network. Our analysis follows ARV's, making essential use of measure concentration on the sphere.



Other Videos By Microsoft Research


2016-08-17Can the Theory of Algorithms Ratify the 'Invisible Hand of the Market'?
2016-08-17eXtreme Research? What might it look like?
2016-08-17For Example
2016-08-17Creating a Considerate World
2016-08-17Anzere: replication policy scaling for personal storage networks
2016-08-17Spectrum Usage Understanding and Dynamic Spectrum Sharing
2016-08-17Getting an Edge at High Speeds: Randomized Algorithms and Networking Hardware
2016-08-17Simple Procurement Mechanisms
2016-08-17Scale-invariant random spatial networks
2016-08-17Optimal Auctions
2016-08-17Breaking the Multicommodity Flow Barrier for ?log(n)-Approximations to Sparsest Cut
2016-08-17Pseudorandom Generators for Regular Branching Programs
2016-08-17Skill Matters: How Web Savvy and Other Factors Influence Online Behavior
2016-08-17Advancing our ability to predict the dynamics of complex natural systems
2016-08-17Cover times, blanket times, and the Gaussian free field
2016-08-17A proof rule for multi-threaded programs
2016-08-17We have it easy, but do we have it right?
2016-08-17Increasing the accessibility of pen-based interaction for older adults
2016-08-17Programs & Projects at the University of Washington Center for Information Assurance & Cybersecurity
2016-08-17The Brave New World of Full Service Computing
2016-08-17Incentive Design in Distributed-Work Systems: Image Labeling Games and Question and Answer Forums


Tags:
microsoft research