Please help transcribe this video using our simple transcription tool. You need to be logged in to do so.

Description

We present a general method of designing fast approximation algorithms for cut-based minimization problems in undirected graphs. In particular, we develop a technique that given any such problem that can be approximated quickly on trees, allows approximating it almost as quickly on general graphs while only losing a poly-logarithmic factor in the approximation guarantee. We present a general method of designing fast approximation algorithms for undirected cut-based minimization problems. More precisely, we develop a technique that given any such cut-based problem that can be approximated quickly on trees, allows approximating it almost as quickly on general graphs while only losing a poly-logarithmic factor in the approximation guarantee.

To illustrate the applicability of our paradigm, we focus our attention on the undirected sparsest cut problem with general demands, and the balanced separator problem. By a simple use of our framework, we obtain poly-logarithmic approximation algorithms for these problems that run in time close to linear. This establishes, in particular, the first poly-logarithmic-approximation algorithm for the generalized sparsest cut problem whose running time breaks the multicommodity flow barrier of $Omega(n^2)$ time, and the first algorithms achieving such approximation ratio for the balanced separator and the (uniform) sparsest cut problem while running in time $o(m+n^{3/2})$.

The main tool behind our result is an efficient procedure that decomposes general graphs into simpler ones while approximately preserving the cut-flow structure. This decomposition is inspired by hierarchical tree decompositions that were developed in the context of oblivious routing schemes.

Questions and Answers

You need to be logged in to be able to post here.