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.
A full version appears at http://arxiv.org/abs/1006.3970
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
- Vertex Cover
- Tree Decomposition
- Linear Programming Relaxation
- General Demand
- Linear Programming Solution
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Arora, S., Bollobás, B., Lovász, L., Tourlakis, I.: Proving integrality gaps without knowing the linear program. Theory of Computing 2(1), 19–51 (2006)
Arora, S., Lee, J.R., Naor, A.: Euclidean distortion and the sparsest cut. J. Amer. Math. Soc. 21(1), 1–21 (2008)
Arora, S., Rao, S., Vazirani, U.: Expander flows, geometric embeddings and graph partitioning. J. ACM 56(2), 1–37 (2009)
Aumann, Y., Rabani, Y.: An O(logk) approximate min-cut max-flow theorem and approximation algorithm. SIAM J. Comput. 27(1), 291–301 (1998)
Bateni, M., Charikar, M., Guruswami, V.: Maxmin allocation via degree lower-bounded arborescences. In: 41st Annual ACM Symposium on Theory of Computing, pp. 543–552. ACM, New York (2009)
Bienstock, D.: Approximate formulations for 0-1 knapsack sets. Oper. Res. Lett. 36(3), 317–320 (2008)
Chakrabarti, A., Jaffe, A., Lee, J.R., Vincent, J.: Embeddings of topological graphs: Lossy invariants, linearization, and 2-sums. In: 49th Annual IEEE Symposium on Foundations of Computer Science, pp. 761–770 (2008)
Charikar, M., Makarychev, K., Makarychev, Y.: Integrality gaps for Sherali-Adams relaxations. In: 41st ACM Symposium on Theory of Computing, pp. 283–292 (2009)
Chawla, S., Krauthgamer, R., Kumar, R., Rabani, Y., Sivakumar, D.: On the hardness of approximating multicut and sparsest-cut. Computational Complexity 15(2), 94–114 (2006)
Chawla, S., Gupta, A., Räcke, H.: Embeddings of negative-type metrics and an improved approximation to generalized sparsest cut. ACM Transactions on Algorithms 4(2) (2008)
Cheeger, J., Kleiner, B., Naor, A.: A (logn)Ω(1) integrality gap for the sparsest cut SDP. In: 50th Annual IEEE Symposium on Foundations of Computer Science, pp. 555–564. IEEE, Los Alamitos (2009)
Chekuri, C., Gupta, A., Newman, I., Rabinovich, Y., Sinclair, A.: Embedding k-outerplanar graphs into ℓ1. SIAM J. Discret. Math. 20(1), 119–136 (2006)
Chekuri, C., Khanna, S., Shepherd, F.B.: A note on multiflows and treewidth. Algorithmica 54(3), 400–412 (2009)
Chekuri, C., Shepherd, B., Weibel, C.: Flow-cut gaps for integer and fractional multiflows. In: 21st ACM-SIAM Symposium on Discrete Algorithms (2010)
Chlamtac, E.: Approximation algorithms using hierarchies of semidefinite programming relaxations. In: 48th Annual IEEE Symposium on Foundations of Computer Science, pp. 691–701 (2007)
Chlamtac, E., Singh, G.: Improved approximation guarantees through higher levels of SDP hierarchies. In: Goel, A., Jansen, K., Rolim, J.D.P., Rubinfeld, R. (eds.) APPROX and RANDOM 2008. LNCS, vol. 5171, pp. 49–62. Springer, Heidelberg (2008)
Devanur, N.R., Khot, S.A., Saket, R., Vishnoi, N.K.: Integrality gaps for sparsest cut and minimum linear arrangement problems. In: 38th Annual ACM Symposium on Theory of Computing, pp. 537–546 (2006)
Fakcharoenphol, J., Talwar, K.: Improved decompositions of graphs with forbidden minors. In: 6th International Workshop on Approximation Algorithms for Combinatorial Optimization, pp. 36–46 (2003)
Georgiou, K., Magen, A., Pitassi, T., Tourlakis, I.: Integrality gaps of 2 - o(1) for vertex cover SDPs in the Lovász-Schrijver hierarchy. In: 48th Annual IEEE Symposium on Foundations of Computer Science, pp. 702–712 (2007)
Gupta, A., Newman, I., Rabinovich, Y., Sinclair, A.: Cuts, trees and ℓ1-embeddings of graphs. Combinatorica 24(2), 233–269 (2004)
Karlin, A.R., Mathieu, C., Thach Nguyen, C.: Integrality Gaps of Linear and Semi-definite Programming Relaxations for Knapsack. CoRR abs/1007.1283 (2010), http://arxiv.org/abs/1007.1283
Khot, S.: On the power of unique 2-prover 1-round games. In: 34th Annual ACM Symposium on the Theory of Computing, pp. 767–775 (July 2002)
Khot, S., Vishnoi, N.K.: The unique games conjecture, integrality gap for cut problems and the embeddability of negative type metrics into ℓ1. In: 46th IEEE Annual Symposium on Foundations of Computer Science, pp. 53–62 (2005)
Klein, P., Plotkin, S.A., Rao, S.: Excluded minors, network decomposition, and multicommodity flow. In: 25th Annual ACM Symposium on Theory of Computing, pp. 682–690 (May 1993)
Krauthgamer, R., Rabani, Y.: Improved lower bounds for embeddings into L 1. SIAM J. Comput. 38(6), 2487–2498 (2009)
Lasserre, J.B.: Semidefinite programming vs. LP relaxations for polynomial programming. Math. Oper. Res. 27(2), 347–360 (2002)
Laurent, M.: A comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre relaxations for 0–1 programming. Math. Oper. Res. 28(3), 470–496 (2003)
Lee, J.R., Sidiropoulos, A.: Pathwidth, trees, and random embeddings. CoRR abs/0910.1409 (2009)
Leighton, T., Rao, S.: Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. J. ACM 46(6), 787–832 (1999)
Linial, N., London, E., Rabinovich, Y.: The geometry of graphs and some of its algorithmic applications. Combinatorica 15(2), 215–245 (1995)
Lovász, L., Schrijver, A.: Cones of matrices and set-functions and 0-1 optimization. SIAM J. Optim. 1(2), 166–190 (1991)
Magen, A., Moharrami, M.: Robust algorithms for maximum independent set on minor-free graphs based on the Sherali-Adams hierarchy. In: Dinur, I., Jansen, K., Naor, J., Rolim, J. (eds.) APPROX 2009. LNCS, vol. 5687, pp. 258–271. Springer, Heidelberg (2009)
Mathieu, C., Sinclair, A.: Sherali-Adams relaxations of the matching polytope. In: 41st Annual ACM Symposium on Theory of Computing. pp. 293–302 (2009)
Milman, V.D., Schechtman, G.: Asymptotic theory of finite-dimensional normed spaces. Springer, Berlin (1986)
Rabinovich, Y.: On average distortion of embedding metrics into the line and into L 1. In: 35th Annual ACM Symposium on Theory of Computing, pp. 456–462 (2003)
Raghavendra, P., Steurer, D.: Integrality gaps for strong SDP relaxations of unique games. In: 50th IEEE Symposium on Foundations of Computer Science, pp. 575–585 (2009)
Schoenebeck, G.: Linear level Lasserre lower bounds for certain k-CSPs. In: 49th IEEE Symposium on Foundations of Computer Science, pp. 593–602 (2008)
Schoenebeck, G., Trevisan, L., Tulsiani, M.: A linear round lower bound for Lovász-Schrijver SDP relaxations of vertex cover. In: 22nd Annual IEEE Conference on Computational Complexity, pp. 205–216 (2007)
Sherali, H.D., Adams, W.P.: A hierarchy of relaxation between the continuous and convex hull representations. SIAM J. Discret. Math. 3(3), 411–430 (1990)
Shmoys, D.: Cut problems and their applications to divide-and-conquer. In: Hochbaum, D. (ed.) Approximation Algorithms for NP-Hard Problems. PWS Publishing Company (1997)
Tulsiani, M.: CSP gaps and reductions in the Lasserre hierarchy. In: 41st Annual ACM Symposium on Theory of Computing, pp. 303–312 (2009)
Vazirani, V.V.: Approximation algorithms. Springer, Berlin (2001)
de la Vega, W.F., Kenyon-Mathieu, C.: Linear programming relaxations of maxcut. In: 18th ACM-SIAM Symposium on Discrete Algorithms, pp. 53–61 (2007)
Wainwright, M.J., Jordan, M.I.: Treewidth-based conditions for exactness of the Sherali-Adams and Lasserre relaxations. Tech. Rep. 671, University of California, Berkeley, Department of Statistics (September 2004)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Chlamtac, E., Krauthgamer, R., Raghavendra, P. (2010). Approximating Sparsest Cut in Graphs of Bounded Treewidth. In: Serna, M., Shaltiel, R., Jansen, K., Rolim, J. (eds) Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. RANDOM APPROX 2010 2010. Lecture Notes in Computer Science, vol 6302. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-15369-3_10
Download citation
DOI: https://doi.org/10.1007/978-3-642-15369-3_10
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-15368-6
Online ISBN: 978-3-642-15369-3
eBook Packages: Computer ScienceComputer Science (R0)