Fast Approximation Algorithms for Cut-based Problems in Undirected Graphs
arXiv:1008.1975
Abstract
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. 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 the cut-based graph decomposition of Räcke that was developed in the context of oblivious routing schemes, as well as, by the construction of the ultrasparsifiers due to Spielman and Teng that was employed to preconditioning symmetric diagonally-dominant matrices.
References in corpus (4)
- Sequential and Parallel Algorithms for Mixed Packing and Covering
- Nearly-Linear Time Algorithms for Preconditioning and Solving Symmetric, Diagonally Dominant Linear Systems
- A Local Clustering Algorithm for Massive Graphs and its Application to Nearly-Linear Time Graph Partitioning
- Nearly Tight Low Stretch Spanning Trees
Cited by in corpus (8)
- An Agent-Based Algorithm exploiting Multiple Local Dissimilarities for Clusters Mining and Knowledge Discovery
- The Sketching Complexity of Graph Cuts
- An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicommodity Generalizations
- Uncertainty quantification in graph-based classification of high dimensional data
- Near-Optimal Distributed Maximum Flow
- Compact Oblivious Routing
- Electrical Flows, Laplacian Systems, and Faster Approximation of Maximum Flow in Undirected Graphs
- Sparsification of Two-Variable Valued CSPs