Stable Approximation Algorithms for the Dynamic Broadcast Range-Assignment Problem

Authors Mark de Berg, Arpan Sadhukhan, Frits Spieksma



PDF
Thumbnail PDF

File

LIPIcs.SWAT.2022.15.pdf
  • Filesize: 0.97 MB
  • 21 pages

Document Identifiers

Author Details

Mark de Berg
  • Department of Mathematics and Computer Science, Eindhoven University of Technology, The Netherlands
Arpan Sadhukhan
  • Department of Mathematics and Computer Science, Eindhoven University of Technology, The Netherlands
Frits Spieksma
  • Department of Mathematics and Computer Science, Eindhoven University of Technology, The Netherlands

Acknowledgements

We thank the reviewers of an earlier version of the paper for pointing us to some important references and for other helpful comments.

Cite AsGet BibTex

Mark de Berg, Arpan Sadhukhan, and Frits Spieksma. Stable Approximation Algorithms for the Dynamic Broadcast Range-Assignment Problem. In 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 227, pp. 15:1-15:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.SWAT.2022.15

Abstract

Let P be a set of points in ℝ^d (or some other metric space), where each point p ∈ P has an associated transmission range, denoted ρ(p). The range assignment ρ induces a directed communication graph G_{ρ}(P) on P, which contains an edge (p,q) iff |pq| ⩽ ρ(p). In the broadcast range-assignment problem, the goal is to assign the ranges such that G_{ρ}(P) contains an arborescence rooted at a designated root node and the cost ∑_{p ∈ P} ρ(p)² of the assignment is minimized. We study the dynamic version of this problem. In particular, we study trade-offs between the stability of the solution - the number of ranges that are modified when a point is inserted into or deleted from P - and its approximation ratio. To this end we introduce the concept of k-stable algorithms, which are algorithms that modify the range of at most k points when they update the solution. We also introduce the concept of a stable approximation scheme, or SAS for short. A SAS is an update algorithm alg that, for any given fixed parameter ε > 0, is k(ε)-stable and that maintains a solution with approximation ratio 1+ε, where the stability parameter k(ε) only depends on ε and not on the size of P. We study such trade-offs in three settings. - For the problem in ℝ¹, we present a SAS with k(ε) = O(1/ε). Furthermore, we prove that this is tight in the worst case: any SAS for the problem must have k(ε) = Ω(1/ε). We also present algorithms with very small stability parameters: a 1-stable (6+2√5)-approximation algorithm - this algorithm can only handle insertions - a (trivial) 2-stable 2-approximation algorithm, and a 3-stable 1.97-approximation algorithm. - For the problem in 𝕊¹ (that is, when the underlying space is a circle) we prove that no SAS exists. This is in spite of the fact that, for the static problem in 𝕊¹, we prove that an optimal solution can always be obtained by cutting the circle at an appropriate point and solving the resulting problem in ℝ¹. - For the problem in ℝ², we also prove that no SAS exists, and we present a O(1)-stable O(1)-approximation algorithm. Most results generalize to when the range-assignment cost is ∑_{p ∈ P} ρ(p)^{α}, for some constant α > 1. All omitted theorems and proofs are available in the full version of the paper [Mark de Berg et al., 2021].

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
Keywords
  • Computational geometry
  • online algorithms
  • broadcast range assignment
  • stable approximation schemes

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Christoph Ambühl. An optimal bound for the MST algorithm to compute energy efficient broadcast trees in wireless networks. In Proc. 32nd International Colloquium on Automata, Languages and Programming (ICALP 2005), volume 3580 of Lecture Notes in Computer Science, pages 1139-1150, 2005. URL: https://doi.org/10.1007/11523468_92.
  2. Mohammad R. Ataei, Amir H. Banihashemi, and Thomas Kunz. Low-complexity energy-efficient broadcasting in one-dimensional wireless networks. IEEE Trans. Veh. Technol., 61(7):3276-3282, 2012. URL: https://doi.org/10.1109/TVT.2012.2204077.
  3. Mostafa A. Bassiouni and Chun-Chin Fang. Dynamic channel allocation for linear macrocellular topology. In Proc. 1999 ACM Symposium on Applied Computing, pages 382-388, 1999. URL: https://doi.org/10.1145/298151.298391.
  4. Ioannis Caragiannis, Christos Kaklamanis, and Panagiotis Kanellopoulos. New results for energy-efficient broadcasting in wireless networks. In Proc. 13th International Symposium on Algorithms and Computation (ISAAC 2002), volume 2518 of Lecture Notes in Computer Science, pages 332-343, 2002. URL: https://doi.org/10.1007/3-540-36136-7_30.
  5. Andrea E. F. Clementi, Pierluigi Crescenzi, Paolo Penna, Gianluca Rossi, and Paola Vocca. On the complexity of computing minimum energy consumption broadcast subgraphs. In Proc. 18th Annual Symposium on Theoretical Aspects of Computer Science (STACS 2001), volume 2010 of Lecture Notes in Computer Science, pages 121-131. Springer, 2001. URL: https://doi.org/10.1007/3-540-44693-1_11.
  6. Andrea E. F. Clementi, Gurvan Huiban, Paolo Penna, Gianluca Rossi, and Yann C. Verhoeven. Some recent theoretical advances and open questions on energy consumption in ad-hoc wireless networks. In Proc. 3rd Workshop on Approximation and Randomization Algorithms in Communication Networks (ARACNE 2002), 2002. Google Scholar
  7. Andrea E. F. Clementi, Miriam Di Ianni, and Riccardo Silvestri. The minimum broadcast range assignment problem on linear multi-hop wireless networks. Theor. Comput. Sci., 299(1-3):751-761, 2003. URL: https://doi.org/10.1016/S0304-3975(02)00538-8.
  8. Andrea E. F. Clementi, Paolo Penna, Afonso Ferreira, Stephane Perennes, and Riccardo Silvestri. The minimum range assignment problem on linear radio networks. Algorithmica, 35(2):95-110, 2003. URL: https://doi.org/10.1007/s00453-002-0985-2.
  9. Andrea E. F. Clementi, Paolo Penna, and Riccardo Silvestri. Hardness results for the power range assignment problem in packet radio networks. In Proc. 3rd International Workshop on Randomization and Approximation Techniques in Computer Science, and 2nd International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (RANDOM-APPROX'99), volume 1671 of Lecture Notes in Computer Science, pages 197-208, 1999. URL: https://doi.org/10.1007/978-3-540-48413-4_21.
  10. Andrea E. F. Clementi, Paolo Penna, and Riccardo Silvestri. The power range assignment problem in radio networks on the plane. In Proc. 17th Annual Symposium on Theoretical Aspects of Computer Science (STACS), volume 1770 of Lecture Notes in Computer Science, pages 651-660, 2000. URL: https://doi.org/10.1007/3-540-46541-3_54.
  11. Gautam K. Das, Sandip Das, and Subhas C. Nandy. Range assignment for energy efficient broadcasting in linear radio networks. Theor. Comput. Sci., 352(1-3):332-341, 2006. URL: https://doi.org/10.1016/j.tcs.2005.11.046.
  12. Gautam K. Das and Subhas C. Nandy. Weighted broadcast in linear radio networks. Inf. Process. Lett., 106(4):136-143, 2008. URL: https://doi.org/10.1016/j.ipl.2007.10.016.
  13. Mark de Berg, Aleksandar Markovic, and Seeun William Umboh. The online broadcast range-assignment problem. In Proc. 31st International Symposium on Algorithms and Computation (ISAAC), volume 181 of LIPIcs, pages 60:1-60:15, 2020. URL: https://doi.org/10.4230/LIPIcs.ISAAC.2020.60.
  14. Mark de Berg, Arpan Sadhukhan, and Frits C. R. Spieksma. Stable approximation algorithms for the dynamic broadcast range-assignment problem. CoRR, abs/2112.05426, 2021. URL: http://arxiv.org/abs/2112.05426.
  15. Bernhard Fuchs. On the hardness of range assignment problems. Networks, 52(4):183-195, 2008. URL: https://doi.org/10.1002/net.20227.
  16. Lefteris M. Kirousis, Evangelos Kranakis, Danny Krizanc, and Andrzej Pelc. Power consumption in packet radio networks. Theor. Comput. Sci., 243(1-2):289-305, 2000. URL: https://doi.org/10.1016/S0304-3975(98)00223-0.
  17. Rudolf Mathar and Jürgen Mattfeldt. Optimal transmission ranges for mobile communication in linear multihop packet radio networks. Wireless Networks, 2(4):329-342, 1996. URL: https://doi.org/10.1007/BF01262051.
  18. Kaveh Pahlavan and Allen H. Levesque. Wireless information networks, Second Edition. Wiley series in telecommunications and signal processing. Wiley-VCH, 2005. Google Scholar
  19. Peter Sanders, Naveen Sivadasan, and Martin Skutella. Online scheduling with bounded migration. Math. Oper. Res., 34(2):481-498, 2009. URL: https://doi.org/10.1287/moor.1090.0381.
  20. Martin Skutella and José Verschae. A robust PTAS for machine covering and packing. In Proc. 18th Annual European Symposium (ESA 201), volume 6346 of Lecture Notes in Computer Science, pages 36-47, 2010. URL: https://doi.org/10.1007/978-3-642-15775-2_4.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail