Fast Approximation Algorithms for Cut-based Problems in Undirected Graphs

Understand

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.
• 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.