Abstract
Harrelson, Hildrum and Rao [11] construct for a given graph a single tree that acts as a flow sparsifier, i.e., it can approximate multicommodity flows in G up to an O(log 2 nloglog n) factor. Many applications that use these trees do not actually require a flow sparsifier but would already work with just having a cut sparsifier. We show how to construct a cut sparsifier that is a single tree and has quality O(log 1.5 nloglog n).
In addition we show a close connection of this problem to the Mincut Linear Arrangement Problem which shows that improving the guarantee to o(log 1.5 n) might be difficult.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Andreev, K., Garrod, C., Golovin, D., Maggs, B., Meyerson, A.: Simultaneous source location. ACM Transactions on Algorithms 6(1) (2009)
Arora, S., Rao, S., Vazirani, U.: Expander flows, geometric embeddings, and graph partitionings. In: Proc. of the 36th STOC, pp. 222–231 (2004)
Bansal, N., Feige, U., Krauthgamer, R., Makarychev, K., Nagarajan, V., Naor, J.S., Schwartz, R.: Min-max graph partitioning and small set expansion. In: Proc. of the 52nd FOCS, pp. 17–26 (2011)
Benczur, A.A., Karger, D.R.: Approximate s-t min-cuts in \(\tilde{O}(n^2)\) time. In: Proc. of the 28th STOC, pp. 47–55 (1996)
Charikar, M., Leighton, F.T., Li, S., Moitra, A.: Vertex sparsifiers and abstract rounding algorithms. In: Proc. of the 51st FOCS, pp. 265–274 (2010)
Chekuri, C., Khanna, S., Shepherd, F.B.: The all-or-nothing multicommodity flow problem. In: Proc. of the 36th STOC, pp. 156–165 (2004)
Chekuri, C., Khanna, S., Shepherd, F.B.: Multicommodity flow, well-linked terminals, and routing problems. In: Proc. of the 37th STOC, pp. 183–192 (2005)
Chuzhoy, J.: On vertex sparsifiers with steiner nodes. In: Proc. of the 44th STOC, pp. 673–688 (2012)
Engelberg, R., Könemann, J., Leonardi, S., Naor, J.S.: Cut problems in graphs with a budget constraint. Journal of Discrete Algorithms 5(2), 262–279 (2007)
Englert, M., Gupta, A., Krauthgamer, R., Räcke, H., Talgam-Cohen, I., Talwar, K.: Vertex sparsifiers: New results from old techniques. In: Serna, M., Shaltiel, R., Jansen, K., Rolim, J. (eds.) APPROX 2010. LNCS, vol. 6302, pp. 152–165. Springer, Heidelberg (2010)
Harrelson, C., Hildrum, K., Rao, S.: A polynomial-time tree decomposition to minimize congestion. In: Proc. of the 15th SPAA, pp. 34–43 (2003)
Khandekar, R., Kortsarz, G., Mirrokni, V.: Advantage of overlapping clusters for minimizing conductance. In: Fernández-Baca, D. (ed.) LATIN 2012. LNCS, vol. 7256, pp. 494–505. Springer, Heidelberg (2012)
Könemann, J., Parekh, O., Segev, D.: A unified approach to approximating partial covering problems. Algorithmica 59(4), 489–509 (2011)
Leighton, F.T., Moitra, A.: Extensions and limits to vertex sparsification. In: Proc. of the 42nd STOC, pp. 47–56 (2010)
Makarychev, K., Makarychev, Y.: Metric extension operators, vertex sparsifiers and Lipschitz extendability. In: Proc. of the 51st FOCS, pp. 255–264 (2010)
Moitra, A.: Approximation algorithms for multicommodity-type problems with guarantees independent of the graph size. In: Proc. of the 50th FOCS, pp. 3–12 (2009)
Räcke, H.: Minimizing congestion in general networks. In: Proc. of the 43rd FOCS, pp. 43–52 (2002)
Räcke, H.: Optimal hierarchical decompositions for congestion minimization in networks. In: Proc. of the 40th STOC, pp. 255–264 (2008)
Stotz, R.: Approximation algorithms for scheduling processes in distributed systems. Master’s thesis, Institut für Informatik, Technische Universität München (2014)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Räcke, H., Shah, C. (2014). Improved Guarantees for Tree Cut Sparsifiers. In: Schulz, A.S., Wagner, D. (eds) Algorithms - ESA 2014. ESA 2014. Lecture Notes in Computer Science, vol 8737. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-44777-2_64
Download citation
DOI: https://doi.org/10.1007/978-3-662-44777-2_64
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-44776-5
Online ISBN: 978-3-662-44777-2
eBook Packages: Computer ScienceComputer Science (R0)