Approximating Sparsest Cut in Graphs of Bounded Treewidth

Eden Chlamtac; Robert Krauthgamer; Prasad Raghavendra

Back

Approximating Sparsest Cut in Graphs of Bounded Treewidth

Conference paper

Peer reviewed

Approximating Sparsest Cut in Graphs of Bounded Treewidth

Eden Chlamtac, Robert Krauthgamer and Prasad Raghavendra

Approximation, Randomization, And Combinatorial Optimization: Algorithms And Techniques, Vol.6302, pp.124-137

13th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2010)/14th International Workshop on Randomization and Computation (RANDOM 2010) (Barcelona, SPAIN, 01/Sep/2010 - 03/Sep/2010)

2010

Abstract

We give the first constant-factor approximation algorithm for Sparsest-Cut with general demands in bounded treewidth graphs. In contrast to previous algorithms, which rely on the flow-cut gap and/or metric embeddings, our approach exploits the Sherali-Adams hierarchy of linear programming relaxations.

Details

Title: Approximating Sparsest Cut in Graphs of Bounded Treewidth
Creators: Eden Chlamtac (null) - 972WIS_INST___83
Robert Krauthgamer (null) - 972WIS_INST___83
Prasad Raghavendra (null)
Resource Type: Conference paper
Publication Details: Approximation, Randomization, And Combinatorial Optimization: Algorithms And Techniques, Vol.6302, pp.124-137; 2010
Number of pages: 14
Language: English
Conference: 13th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2010)/14th International Workshop on Randomization and Computation (RANDOM 2010) (Barcelona, SPAIN, 01/Sep/2010 - 03/Sep/2010)
Record Identifier: 993264509103596

Metrics

7 Record Views