IDEAS home Printed from https://ideas.repec.org/a/inm/orijoc/v34y2022i5p2675-2685.html
   My bibliography  Save this article

Constant Approximation for the Lifetime Scheduling Problem of p -Percent Coverage

Author

Listed:
  • Zhao Zhang

    (College of Mathematics and Computer Science, Zhejiang Normal University, 321004 Jinhua, Zhejiang, China)

  • Wei Liang

    (College of Mathematics and Computer Science, Zhejiang Normal University, 321004 Jinhua, Zhejiang, China)

  • Hongmin W. Du

    (Accounting and Information Systems Department, Rutgers Business School–Newark, Rutgers University, Newark, New Jersey 07102)

  • Siwen Liu

    (School of Management, Hefei University of Technology, 230009 Hefei, China)

Abstract

It has been an open question for some time whether there exists a polynomial-time constant approximation for the lifetime scheduling problem of p -percent coverage. In this paper, we give a positive answer to this question.

Suggested Citation

  • Zhao Zhang & Wei Liang & Hongmin W. Du & Siwen Liu, 2022. "Constant Approximation for the Lifetime Scheduling Problem of p -Percent Coverage," INFORMS Journal on Computing, INFORMS, vol. 34(5), pages 2675-2685, September.
    • Handle: RePEc:inm:orijoc:v:34:y:2022:i:5:p:2675-2685
    DOI: 10.1287/ijoc.2022.1201
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/ijoc.2022.1201
    Download Restriction: no
    File URL: https://libkey.io/10.1287/ijoc.2022.1201?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Yaochun Huang & Xiaofeng Gao & Zhao Zhang & Weili Wu, 2009. "A better constant-factor approximation for weighted dominating set in unit disk graph," Journal of Combinatorial Optimization, Springer, vol. 18(2), pages 179-194, August.
    2. Weili Wu & Zhao Zhang & Wonjun Lee & Ding-Zhu Du, 2020. "Optimal Coverage in Wireless Sensor Networks," Springer Optimization and Its Applications, Springer, number 978-3-030-52824-9, June.
    3. Yingli Ran & Zhao Zhang & Ker-I Ko & Jun Liang, 2016. "An approximation algorithm for maximum weight budgeted connected set cover," Journal of Combinatorial Optimization, Springer, vol. 31(4), pages 1505-1517, May.
    4. Peng Du & Yuan Zhang, 2016. "A New Distributed Approximation Algorithm for the Maximum Weight Independent Set Problem," Mathematical Problems in Engineering, Hindawi, vol. 2016, pages 1-10, September.
    5. Yingli Ran & Zhao Zhang & Shaojie Tang & Ding-Zhu Du, 2021. "Breaking the r max Barrier: Enhanced Approximation Algorithms for Partial Set Multicover Problem," INFORMS Journal on Computing, INFORMS, vol. 33(2), pages 774-784, May.
    6. Yingli Ran & Xiaohui Huang & Zhao Zhang & Ding-Zhu Du, 2021. "Approximation algorithm for minimum power partial multi-coverage in wireless sensor networks," Journal of Global Optimization, Springer, vol. 80(3), pages 661-677, July.
    7. Zhao Zhang & Jiao Zhou & Shaojie Tang & Xiaohui Huang & Ding-Zhu Du, 2018. "Computing Minimum k -Connected m -Fold Dominating Set in General Graphs," INFORMS Journal on Computing, INFORMS, vol. 30(2), pages 217-224, May.
    8. Jiao Zhou & Zhao Zhang & Shaojie Tang & Xiaohui Huang & Ding-Zhu Du, 2018. "Breaking the O (ln n ) Barrier: An Enhanced Approximation Algorithm for Fault-Tolerant Minimum Weight Connected Dominating Set," INFORMS Journal on Computing, INFORMS, vol. 30(2), pages 225-235, May.
    9. Yishuo Shi & Yingli Ran & Zhao Zhang & James Willson & Guangmo Tong & Ding-Zhu Du, 2019. "Approximation algorithm for the partial set multi-cover problem," Journal of Global Optimization, Springer, vol. 75(4), pages 1133-1146, December.
    10. Hongwei Du & Panos Pardalos & Weili Wu & Lidong Wu, 2013. "Maximum lifetime connected coverage with two active-phase sensors," Journal of Global Optimization, Springer, vol. 56(2), pages 559-568, June.
    11. Xiaojun Zhu & Guihai Chen & Shaojie Tang & Xiaobing Wu & Bing Chen, 2016. "Fast Approximation Algorithm for Maximum Lifetime Aggregation Trees in Wireless Sensor Networks," INFORMS Journal on Computing, INFORMS, vol. 28(3), pages 417-431, August.
    12. Ding-Zhu Du & Ker-I Ko & Xiaodong Hu, 2012. "Design and Analysis of Approximation Algorithms," Springer Optimization and Its Applications, Springer, number 978-1-4614-1701-9, June.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Yaoyao Zhang & Zhao Zhang & Ding-Zhu Du, 2023. "Construction of minimum edge-fault tolerant connected dominating set in a general graph," Journal of Combinatorial Optimization, Springer, vol. 45(2), pages 1-12, March.
    2. Xiaozhi Wang & Xianyue Li & Bo Hou & Wen Liu & Lidong Wu & Suogang Gao, 2021. "A greedy algorithm for the fault-tolerant outer-connected dominating set problem," Journal of Combinatorial Optimization, Springer, vol. 41(1), pages 118-127, January.
    3. Yubai Zhang & Yingli Ran & Zhao Zhang, 2017. "A simple approximation algorithm for minimum weight partial connected set cover," Journal of Combinatorial Optimization, Springer, vol. 34(3), pages 956-963, October.
    4. Yingli Ran & Xiaohui Huang & Zhao Zhang & Ding-Zhu Du, 2021. "Approximation algorithm for minimum power partial multi-coverage in wireless sensor networks," Journal of Global Optimization, Springer, vol. 80(3), pages 661-677, July.
    5. Yingli Ran & Zhao Zhang & Shaojie Tang & Ding-Zhu Du, 2021. "Breaking the r max Barrier: Enhanced Approximation Algorithms for Partial Set Multicover Problem," INFORMS Journal on Computing, INFORMS, vol. 33(2), pages 774-784, May.
    6. Xiaojun Zhu & Shaojie Tang, 2021. "Exact Algorithms for the Minimum Load Spanning Tree Problem," INFORMS Journal on Computing, INFORMS, vol. 33(4), pages 1431-1445, October.
    7. Amir Masoud Rahmani & Saqib Ali & Mohammad Sadegh Yousefpoor & Efat Yousefpoor & Rizwan Ali Naqvi & Kamran Siddique & Mehdi Hosseinzadeh, 2021. "An Area Coverage Scheme Based on Fuzzy Logic and Shuffled Frog-Leaping Algorithm (SFLA) in Heterogeneous Wireless Sensor Networks," Mathematics, MDPI, vol. 9(18), pages 1-41, September.
    8. Feng Zou & Xianyue Li & Suogang Gao & Weili Wu, 2009. "Node-weighted Steiner tree approximation in unit disk graphs," Journal of Combinatorial Optimization, Springer, vol. 18(4), pages 342-349, November.
    9. Hongwei Du & Panos Pardalos & Weili Wu & Lidong Wu, 2013. "Maximum lifetime connected coverage with two active-phase sensors," Journal of Global Optimization, Springer, vol. 56(2), pages 559-568, June.
    10. Guang Zhu & Hu Liu & Mining Feng, 2018. "An Evolutionary Game-Theoretic Approach for Assessing Privacy Protection in mHealth Systems," IJERPH, MDPI, vol. 15(10), pages 1-27, October.
    11. Zhao Zhang & Wen Xu & Weili Wu & Ding-Zhu Du, 2017. "A novel approach for detecting multiple rumor sources in networks with partial observations," Journal of Combinatorial Optimization, Springer, vol. 33(1), pages 132-146, January.
    12. Majun Shi & Zishen Yang & Wei Wang, 2023. "Greedy guarantees for minimum submodular cost submodular/non-submodular cover problem," Journal of Combinatorial Optimization, Springer, vol. 45(1), pages 1-16, January.
    13. Jiao Zhou & Zhao Zhang & Weili Wu & Kai Xing, 2014. "A greedy algorithm for the fault-tolerant connected dominating set in a general graph," Journal of Combinatorial Optimization, Springer, vol. 28(1), pages 310-319, July.
    14. Kübra Tanınmış & Markus Sinnl, 2022. "A Branch-and-Cut Algorithm for Submodular Interdiction Games," INFORMS Journal on Computing, INFORMS, vol. 34(5), pages 2634-2657, September.
    15. Xiao Zhang & Haosheng Fan & Victor C. S. Lee & Minming Li & Yingchao Zhao & Chuang Liu, 2018. "Minimizing the total cost of barrier coverage in a linear domain," Journal of Combinatorial Optimization, Springer, vol. 36(2), pages 434-457, August.
    16. Hejiao Huang & Feng Shang & Jinling Liu & Hongwei Du, 2015. "Handling least privilege problem and role mining in RBAC," Journal of Combinatorial Optimization, Springer, vol. 30(1), pages 63-86, July.
    17. Xiang Li & H. George Du & Panos M. Pardalos, 2020. "A variation of DS decomposition in set function optimization," Journal of Combinatorial Optimization, Springer, vol. 40(1), pages 36-44, July.
    18. Xiang Li & H. George Du, 2020. "A short proof for stronger version of DS decomposition in set function optimization," Journal of Combinatorial Optimization, Springer, vol. 40(4), pages 901-906, November.
    19. Chuanwen Luo & Yongcai Wang & Yi Hong & Wenping Chen & Xingjian Ding & Yuqing Zhu & Deying Li, 2019. "Minimizing data collection latency with unmanned aerial vehicle in wireless sensor networks," Journal of Combinatorial Optimization, Springer, vol. 38(4), pages 1019-1042, November.
    20. Shi, Majun & Yang, Zishen & Wang, Wei, 2021. "Minimum non-submodular cover problem with applications," Applied Mathematics and Computation, Elsevier, vol. 410(C).

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:orijoc:v:34:y:2022:i:5:p:2675-2685. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.