SpringerLink
Log in

An Approximation Algorithm for Stochastic Power Cover Problem

  • Conference paper
  • First Online:
Theoretical Computer Science (NCTCS 2023)

Part of the book series: Communications in Computer and Information Science ((CCIS,volume 1944))

Included in the following conference series:

  • 138 Accesses

Abstract

In this paper, we introduce the stochastic power cover (SPC) problem, which aims to determine the two-stage power assignment and minimize the total expected power consumption. For this problem, we are given a set U of n users, a set S of m sensors on the plane and k possible scenarios, where k is a polynomial and each consists of a probability of occurrence. Each sensor \(s\in S\) can adjust the power it produces by changing its radius and the relationship between them satisfies the following power equation \(p\left( s \right) =c\cdot r \left( s \right) ^{\alpha }\). The objective is to identify the radius of each sensor in the first stage and augment the first-stage solution in order to cover all users and minimize the expected power over both stages. Our main result is to present an O(\(\alpha \))-approximation algorithm by using the primal-dual technique.

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
EUR 32.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 (Canada)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 59.99
Price excludes VAT (Canada)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 79.99
Price excludes VAT (Canada)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free ship** worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  1. Charikar, M., Panigrahy, R.: Clustering to minimize the sum of cluster diameters. J. Comput. Syst. Sci. 68(2), 417–441 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  2. Bilò, V., Caragiannis, I., Kaklamanis, C., Kanellopoulos, P.: Geometric clustering to minimize the sum of cluster sizes. In: Brodal, G.S., Leonardi, S. (eds.) ESA 2005. LNCS, vol. 3669, pp. 460–471. Springer, Heidelberg (2005). https://doi.org/10.1007/11561071_42

    Chapter  Google Scholar 

  3. Ravi, R., Sinha, A.: Hedging uncertainty: approximation algorithms for stochastic optimization problems. Math. Program. 108(1), 97–114 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  4. Li, J., Liu, Y.: Approximation algorithms for stochastic combinatorial optimization problems. J. Oper. Res. Soc. China 4(1), 1–47 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  5. Parthasarathy, S.: Adaptive greedy algorithms for stochastic set cover problems. ar**v preprint ar**v:1803.07639 (2018)

  6. Sun, J., Sheng, H., Sun, Y., et al.: Approximation algorithms for stochastic set cover and single sink rent-or-buy with submodular penalty. J. Comb. Optim. 44(4), 2626–2641 (2022)

    Article  MathSciNet  MATH  Google Scholar 

  7. Liu, X., Li, W., **e, R.: A primal-dual approximation algorithm for the k-prize-collecting minimum power cover problem. Optim. Lett. 16(8), 2373–2385 (2022)

    Article  MathSciNet  MATH  Google Scholar 

  8. Dai, H., Deng, B., Li, W., Liu, X.: A note on the minimum power partial cover problem on the plane. J. Comb. Optim. 44(2), 970–978 (2022)

    Article  MathSciNet  MATH  Google Scholar 

  9. Liu, X., Li, W., Dai, H.: Approximation algorithms for the minimum power cover problem with submodular/linear penalties. Theoret. Comput. Sci. 923, 256–270 (2022)

    Article  MathSciNet  MATH  Google Scholar 

  10. Dai, H.: An improved approximation algorithm for the minimum power cover problem with submodular penalty. Computation 10(10), 189 (2022)

    Article  Google Scholar 

  11. Liu, X., Dai, H., Li, S., Li, W.: The k-prize-collecting minimum power cover problem with submodular penalties on a plane. Sci. Sin. Inform 52(6), 947–959 (2022)

    Article  Google Scholar 

  12. Zhang, Q., Li, W., Su, Q., Zhang, X.: A primal-dual-based power control approach for capacitated edge servers. Sensors 22(19), 7582 (2022)

    Article  Google Scholar 

  13. Liu, X., Li, W.: Combinatorial approximation algorithms for the submodular multicut problem in trees with submodular penalties. J. Comb. Optim. 44(3), 1964–1976 (2020)

    Article  MathSciNet  MATH  Google Scholar 

  14. Liu, X., Li, W., Yang, J.: A primal-dual approximation algorithm for the k-prize-collecting minimum vertex cover problem with submodular penalties. Front. Comp. Sci. 17(3), 1–8 (2023)

    Google Scholar 

  15. Kong, N., Schaefer, A.J.: A factor 12 approximation algorithm for two-stage stochastic matching problems. Eur. J. Oper. Res. 172(3), 740–746 (2006)

    Article  MATH  Google Scholar 

  16. Li, M., Ran, Y., Zhang, Z.: A primal-dual algorithm for the minimum power partial cover problem. J. Combi. Optim. 44(3), 1913–1923 (2020)

    Article  MathSciNet  MATH  Google Scholar 

  17. Louveaux, F.V., Peeters, D.: A dual-based procedure for stochastic facility location. Oper. Res. 40(3), 564–573 (1992)

    Article  MathSciNet  MATH  Google Scholar 

  18. Takazawa, Y.: Approximation algorithm for the stochastic prize-collecting set multicover problem. Oper. Res. Lett. 50(2), 224–228 (2022)

    Article  MathSciNet  MATH  Google Scholar 

  19. Le Cam, L.: An approximation theorem for the poisson binomial distribution. Pac. J. Math. 10(4), 1181–1197 (1960)

    Article  MathSciNet  MATH  Google Scholar 

  20. Alt, H., Arkin, E M, Brönnimann H, et al. Minimum-cost coverage of point sets by disks. In: Proceedings of the Twenty-Second Annual Symposium on Computational Geometry, pp. 449–458 (2006)

    Google Scholar 

  21. Dai, H., Li, W., Liu, X.: An approximation algorithm for the h-prize-collecting power cover problem. In: Li, M., Sun, X. (eds.) Frontiers of Algorithmic Wisdom. IJTCS-FAW 2022. LNCS, vol. 13461, pp. 89–98. Springer, Cham (2022). https://doi.org/10.1007/978-3-031-20796-9_7

  22. Dai, H.: An Approximation Algorithm for the Minimum Soft Capacitated Disk Multi-coverage Problem. In: 40th National Conference of Theoretical Computer Science, pp. 96–104. Springer, Changchun (2022)

    Google Scholar 

  23. Zhang, Q., Li, W., Su, Q., Zhang, X.: A local-ratio-based power control approach for capacitated access points in mobile edge computing. In: Proceedings of the 6th International Conference on High Performance Compilation, Computing and Communications, pp. 175–182 (2022)

    Google Scholar 

  24. Gupta, A., Pál, M., Ravi, R., Sinha, A.: Boosted sampling: approximation algorithms for stochastic optimization. In: Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing, pp. 417–426 (2004)

    Google Scholar 

  25. Charikar, M., Chekuri, C., Pal, M.: Sampling bounds for stochastic optimization. In: 8th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, pp. 257–269. Springer, Berkeley (2005)

    Google Scholar 

  26. Feldman, M., Svensson, O., Zenklusen R.: Online contention resolution schemes. In: Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms, pp. 1014–1033 (2016)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. School of Mathematics and Statistics, Yunnan University, Kunming, 650500, China

    Menghan Cao

Authors
  1. Menghan Cao
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Menghan Cao .

Editor information

Editors and Affiliations

  1. National University of Defense Technology, Changsha, China

    Zhi** Cai

  2. University of Electronic Science and Technology, Chengdu, China

    Mingyu **ao

  3. Chinese Academy of Sciences, Bei**g, China

    Jialin Zhang

Rights and permissions

Reprints and permissions

Copyright information

© 2024 The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd.

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Cao, M. (2024). An Approximation Algorithm for Stochastic Power Cover Problem. In: Cai, Z., **ao, M., Zhang, J. (eds) Theoretical Computer Science. NCTCS 2023. Communications in Computer and Information Science, vol 1944. Springer, Singapore. https://doi.org/10.1007/978-981-99-7743-7_6

Download citation

  • DOI: https://doi.org/10.1007/978-981-99-7743-7_6

  • Published:

  • Publisher Name: Springer, Singapore

  • Print ISBN: 978-981-99-7742-0

  • Online ISBN: 978-981-99-7743-7

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Societies and partnerships

Search

Navigation