Nothing Special   »   [go: up one dir, main page]

Skip to main content

Abstract

Given a capacitated graph G = (V,E) and a set of terminals K ⊆ V, how should we produce a graph H only on the terminals K so that every (multicommodity) flow between the terminals in G could be supported in H with low congestion, and vice versa? (Such a graph H is called a flow-sparsifier for G.) What if we want H to be a “simple” graph? What if we allow H to be a convex combination of simple graphs?

Improving on results of Moitra [FOCS 2009] and Leighton and Moitra [STOC 2010], we give efficient algorithms for constructing: (a) a flow-sparsifier H that maintains congestion up to a factor of \({\smash{O(\frac{\log k}{\log \log k})}}\), where k = |K|. (b) a convex combination of trees over the terminals K that maintains congestion up to a factor of O(logk). (c) for a planar graph G, a convex combination of planar graphs that maintains congestion up to a constant factor. This requires us to give a new algorithm for the 0-extension problem, the first one in which the preimages of each terminal are connected in G. Moreover, this result extends to minor-closed families of graphs.

Our bounds immediately imply improved approximation guarantees for several terminal-based cut and ordering problems.

A full version appears at http://arxiv.org/abs/1006.4586

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 84.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 109.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Andersen, R., Feige, U.: Interchanging distance and capacity in probabilistic mappings. CoRR, abs/0907.3631 (2009)

    Google Scholar 

  2. Archer, A., Fakcharoenphol, J., Harrelson, C., Krauthgamer, R., Talwar, K., Tardos, É.: Approximate classification via earthmover metrics. In: Proc. 15th SODA, pp. 1079–1087 (2004)

    Google Scholar 

  3. Calinescu, G., Karloff, H.J., Rabani, Y.: Approximation algorithms for the 0-extension problem. SIAM J. Comput. 34(2), 358–372 (2004)

    Article  MATH  MathSciNet  Google Scholar 

  4. Fakcharoenphol, J., Harrelson, C., Rao, S., Talwar, K.: An improved approximation algorithm for the 0-extension problem. In: Proc. 14th SODA, pp. 257–265 (2003)

    Google Scholar 

  5. Fakcharoenphol, J., Rao, S., Talwar, K.: A tight bound on approximating arbitrary metrics by tree metrics. J. Comput. System Sci. 69(3), 485–497 (2004)

    Article  MATH  MathSciNet  Google Scholar 

  6. Fakcharoenphol, J., Talwar, K.: Improved decompositions of graphs with forbidden minors. In: Arora, S., Jansen, K., Rolim, J.D.P., Sahai, A. (eds.) 6th APPROX. LNCS, vol. 2764, pp. 36–46. Springer, Heidelberg (2003)

    Google Scholar 

  7. Gupta, A., Nagarajan, V., Ravi, R.: Improved approximation algorithms for requirement cut. Operations Research Letters 38(4), 322–325 (2010)

    Article  Google Scholar 

  8. Gupta, A., Newman, I., Rabinovich, Y., Sinclair, A.: Cuts, trees and ℓ1-embeddings of graphs. Combinatorica 24(2), 233–269 (2004)

    Article  MATH  MathSciNet  Google Scholar 

  9. Gupta, A.: Steiner points in tree metrics don’t (really) help. In: Proc. 12th SODA, pp. 220–227 (2001)

    Google Scholar 

  10. Klein, P., Plotkin, S.A., Rao, S.B.: Excluded minors, network decomposition, and multicommodity flow. In: Proc. 25th STOC, pp. 682–690 (1993)

    Google Scholar 

  11. Leighton, T., Moitra, A.: Extensions and limits to vertex sparsification. In: Proc. 42th STOC, pp. 47–56 (2010)

    Google Scholar 

  12. Lee, J.R., Naor, A.: Extending Lipschitz functions via random metric partitions. Invent. Math. 160(1), 59–95 (2005)

    Article  MATH  MathSciNet  Google Scholar 

  13. Lee, J.R., Sidiropoulos, A.: On the geometry of graphs with a forbidden minor. In: Proc. 41st STOC, pp. 245–254 (2009)

    Google Scholar 

  14. Moitra, A.: Approximation algorithms for multicommodity-type problems with guarantees independent of the graph size. In: Proc. 50th FOCS, pp. 3–12 (2009)

    Google Scholar 

  15. Nowozin, S., Lampert, C.H.: Global connectivity potentials for random field models. In: Proc. 22nd CVPR, pp. 818–825 (2009)

    Google Scholar 

  16. Räcke, H.: Optimal hierarchical decompositions for congestion minimization in net works. In: Proc. 40th STOC, pp. 255–264 (2008)

    Google Scholar 

  17. Vicente, S., Kolmogorov, V., Rother, C.: Graph cut based image segmentation with connectivity priors. In: Proc. 21st CVPR (2008)

    Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Editor information

Editors and Affiliations

Rights and permissions

Reprints and permissions

Copyright information

© 2010 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Englert, M., Gupta, A., Krauthgamer, R., Räcke, H., Talgam-Cohen, I., Talwar, K. (2010). Vertex Sparsifiers: New Results from Old Techniques. 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_12

Download citation

  • DOI: https://doi.org/10.1007/978-3-642-15369-3_12

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

Publish with us

Policies and ethics