Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Plane Gossip: Approximating Rumor Spread in Planar Graphs

  • Conference paper
  • First Online:
LATIN 2018: Theoretical Informatics (LATIN 2018)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 10807))

Included in the following conference series:

Abstract

We study the design of schedules for multi-commodity multicast. In this problem, we are given an undirected graph G and a collection of source-destination pairs, and the goal is to schedule a minimum-length sequence of matchings that connects every source with its respective destination. The primary communication constraint of the multi-commodity multicast model is the number of connections that a given node can make, not link bandwidth. Multi-commodity multicast and its special cases, (single-commodity) broadcast and multicast, are all NP-complete. Multi-commodity multicast is closely related to the problem of finding a subgraph of optimal poise, where the poise is defined as the sum of the maximum degree and the maximum distance between any source-destination pair. We show that for any instance of the multicast problem, the minimum poise subgraph can be approximated to within a factor of \(O(\log k)\) with respect to the value of a natural LP relaxation in a graph with k source-destination pairs. This is the first upper bound on the integrality gap of the natural LP; all previous algorithms yielded approximations with respect to the integer optimum. Using this integrality gap upper bound and shortest-path separators in planar graphs, we obtain our main result: an \(O(\log ^3 k \frac{\log n}{\log \log n})\)-approximation for multi-commodity multicast for planar graphs which improves on the \(2^{\widetilde{O}(\sqrt{\log n})}\)-approximation for general graphs.

We also study the minimum-time radio gossip problem in planar graphs where a message from each node must be transmitted to all other nodes under a model where nodes can broadcast to all neighbors and only nodes with a single broadcasting neighbor get a non-interfered message. In earlier work Iglesias et al. (FSTTCS 2015), we showed a strong \(\varOmega (n^{\frac{1}{2} - \epsilon })\)-hardness of approximation for computing a minimum gossip schedule in general graphs. Using our techniques for the telephone model, we give an \(O(\log ^2 n)\)-approximation for radio gossip in planar graphs breaking this barrier. Moreover, this is the first bound for radio gossip given that doesn’t rely on the maximum degree of the graph.

This material is based upon research supported in part by the U. S. Office of Naval Research under award number N00014-12-1-1001 and National Science Foundation under award number CCF-1527032.

J. Iglesias—Now at Waymo. This material is based upon work supported by the National Science Foundation Graduate Research Fellowship Program under Grant No. 2013170941.

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

Access this chapter

Log in via an institution

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 39.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 54.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

Similar content being viewed by others

Notes

  1. 1.

    Even though the number of path variables is exponential, it is not hard to convert this to a compact formulation on the edge variables that can be solved in polynomial time. See e.g., [30].

References

  1. Abraham, I., Gavoille, C.: Object location using path separators. In: PODC, pp. 188–197 (2006)

    Google Scholar 

  2. Alon, N., Bar-Noy, A., Linial, N., Peleg, D.: A lower bound for radio broadcast. J. Comput. Syst. Sci. 43, 290–298 (1991)

    Article  MathSciNet  MATH  Google Scholar 

  3. Baker, B., Shostak, R.: Gossips and telephones. Discret. Math. 2(3), 191–193 (1972)

    Article  MathSciNet  MATH  Google Scholar 

  4. Bar-Noy, A., Guha, S., Naor, J., Schieber, B.: Message multicasting in heterogeneous networks. SIAM J. Comput. 30(2), 347–358 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  5. Cherkassky, B.: Mnogopolyusnye dvukhproduktovye zadachi [Russian: Multiterminal two commodity problems]. Issledovaniya po Diskretnoi Optimizatsii [Russian: Studies in discrete optimization], pp. 261–289 (1976)

    Google Scholar 

  6. Elkin, M., Kortsarz, G.: A combinatorial logarithmic approximation algorithm for the directed telephone broadcast problem. SIAM J. Comput. 35(3), 672–689 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  7. Elkin, M., Kortsarz, G.: Polylogarithmic additive inapproximability of the radio broadcast problem. SIAM J. Discret. Math. 19(4), 881–899 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  8. Elkin, M., Kortsarz, G.: An approximation algorithm for the directed telephone multicast problem. Algorithmica 45(4), 569–583 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  9. Elkin, M., Kortsarz, G.: Sublogarithmic approximation for telephone multicast. J. Comput. Syst. Sci. 72(4), 648–659 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  10. Feige, U., Peleg, D., Raghavan, P., Upfal, E.: Randomized broadcast in networks. Random Struct. Algorithms 1(4), 447–460 (1990)

    Article  MathSciNet  MATH  Google Scholar 

  11. Fountoulakis, N., Panagiotou, K., Sauerwald, T.: Ultra-fast rumor spreading in social networks. In: SODA 2012, pp. 1642–1660. SIAM (2012)

    Google Scholar 

  12. Frank, A.: Connections in Combinatorial Optimization. Oxford Lecture Series in Mathematics and Its Applications. OUP Oxford, Oxford (2011)

    MATH  Google Scholar 

  13. Gąsieniec, L.: On efficient gossiping in radio networks. In: Kutten, S., Žerovnik, J. (eds.) SIROCCO 2009. LNCS, vol. 5869, pp. 2–14. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-11476-2_2

    Chapter  Google Scholar 

  14. Gasieniec, L., Peleg, D., Xin, Q.: Faster communication in known topology radio networks. Distrib. Comput. 19(4), 289–300 (2007)

    Article  MATH  Google Scholar 

  15. Giakkoupis, G.: Tight bounds for rumor spreading in graphs of a given conductance. In: STACS 2011, vol. 9, pp. 57–68 (2011)

    Google Scholar 

  16. Grigni, M., Peleg, D.: Tight bounds on minimum broadcast networks. SIAM J. Discret. Math. 4(2), 207–222 (1991)

    Article  MathSciNet  MATH  Google Scholar 

  17. Hajnal, A., Milner, E.C., Szemerédi, E.: A cure for the telephone disease. Canad. Math. Bull 15(3), 447–450 (1972)

    Article  MathSciNet  MATH  Google Scholar 

  18. Iglesias, J., Rajaraman, R., Ravi, R., Sundaram, R.: Rumors across radio, wireless, telephone. In: FSTTCS, pp. 517–528 (2015)

    Google Scholar 

  19. Iglesias, J., Rajaraman, R., Ravi, R., Sundaram, R.: Plane gossip: Approximating rumor spread in planar graphs. CoRR, abs/1612.01492 (2016)

    Google Scholar 

  20. Karp, R., Schindelhauer, C., Shenker, S., Vocking, B.: Randomized rumor spreading. In: FOCS 2000, Washington, DC, USA, pp. 565–574. IEEE (2000)

    Google Scholar 

  21. Karp, R.M., Leighton, F.T., Rivest, R.L., Thompson, C.D., Vazirani, U.V., Vazirani, V.V.: Global wire routing in two-dimensional arrays. Algorithmica 2(1), 113–129 (1987)

    Article  MathSciNet  MATH  Google Scholar 

  22. Kortsarz, G., Peleg, D.: Approximation algorithms for minimum-time broadcast. SIAM J. Discret. Math. 8(3), 401–427 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  23. Kowalski, D.R., Pelc, A.: Optimal deterministic broadcasting in known topology radio networks. Distrib. Comput. 19(3), 185–195 (2007)

    Article  MATH  Google Scholar 

  24. Lipton, R.J., Tarjan, R.E.: A separator theorem for planar graphs. SIAM J. Appl. Math. 36(2), 177–189 (1979)

    Article  MathSciNet  MATH  Google Scholar 

  25. Lovász, L.: On some connectivity properties of Eulerian graphs. Acta Math. Acad. Sci. Hung. 28, 129–138 (1976)

    Article  MathSciNet  MATH  Google Scholar 

  26. Manne, F., Wang, S., Xin, Q.: Faster radio broadcast in planar graphs. In: WONS, pp. 9–13 (2008)

    Google Scholar 

  27. Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge International Series on Parallel Computation. Cambridge University Press, Cambridge (1995)

    Book  MATH  Google Scholar 

  28. Nikzad, A., Ravi, R.: Sending secrets swiftly: approximation algorithms for generalized multicast problems. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds.) ICALP 2014. LNCS, vol. 8573, pp. 568–607. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-43951-7_48

    Google Scholar 

  29. Proskurowski, A.: Minimum broadcast trees. IEEE Trans. Comput. 30(5), 363–366 (1981)

    Article  Google Scholar 

  30. Ravi, R.: Rapid rumor ramification: approximating the minimum broadcast time. In: FOCS, pp. 202–213. IEEE (1994)

    Google Scholar 

  31. Ravi, R.: Matching based augmentations for approximating connectivity problems. In: Correa, J.R., Hevia, A., Kiwi, M. (eds.) LATIN 2006. LNCS, vol. 3887, pp. 13–24. Springer, Heidelberg (2006). https://doi.org/10.1007/11682462_4

    Chapter  Google Scholar 

  32. Thorup, M.: Compact oracles for reachability and approximate distances in planar digraphs. J. ACM 51(6), 993–1024 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  33. Tijdeman, R.: On a telephone problem. Nieuw Archief voor Wiskunde 3(19), 188–192 (1971)

    MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Carnegie Mellon University, Pittsburgh, PA, USA

    Jennifer Iglesias & R. Ravi

  2. Northeastern University, Boston, MA, USA

    Rajmohan Rajaraman & Ravi Sundaram

Authors
  1. Jennifer Iglesias
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Rajmohan Rajaraman
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. R. Ravi
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Ravi Sundaram
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Jennifer Iglesias .

Editor information

Editors and Affiliations

  1. Stony Brook University, Stony Brook, New York, USA

    Michael A. Bender

  2. Rutgers University, New Brunswick, New Jersey, USA

    Martín Farach-Colton

  3. Pace University, New York, New York, USA

    Miguel A. Mosteiro

Rights and permissions

Reprints and permissions

Copyright information

© 2018 Springer International Publishing AG, part of Springer Nature

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Iglesias, J., Rajaraman, R., Ravi, R., Sundaram, R. (2018). Plane Gossip: Approximating Rumor Spread in Planar Graphs. In: Bender, M., Farach-Colton, M., Mosteiro, M. (eds) LATIN 2018: Theoretical Informatics. LATIN 2018. Lecture Notes in Computer Science(), vol 10807. Springer, Cham. https://doi.org/10.1007/978-3-319-77404-6_45

Download citation

  • DOI: https://doi.org/10.1007/978-3-319-77404-6_45

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-319-77403-9

  • Online ISBN: 978-3-319-77404-6

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation