Approximation Algorithm for the Minimum Interval Partial Multi-Cover Problem

被引：0
|
作者：
Ran, Yingli [1 ]
Jin, Jianhong [1 ]
Zhang, Zhao [1 ]
机构：
[1] Zhejiang Normal Univ, Sch Math Sci, Jinhua, Zhejiang, Peoples R China
来源：
NETWORKS | 2024年
关键词：
approximation algorithm; interval cover; partial set multi-cover; densest k subgraph;
D O I：
10.1002/net.22263
中图分类号：
TP3 [计算技术、计算机技术];
学科分类号：
0812 ;
摘要：
Given a set of points on a line, a set of intervals along the line and an integer k, each point p is associated with a covering requirement cr(p), the goal of the minimum interval partial multi-cover (MinIPMC) problem is to select the minimum number of intervals to fully cover at least k points, where a point p is fully covered if it belongs to at least cr(p) selected intervals. This paper presents a 2-approximation algorithm for the MinIPMC problem.
引用
收藏
页码：288 / 293
页数：6
相关论文
共 50 条
  • [31] A New Approximation Algorithm for Vertex Cover Problem
    Dahiya, Sonika
    2013 INTERNATIONAL CONFERENCE ON MACHINE INTELLIGENCE AND RESEARCH ADVANCEMENT (ICMIRA 2013), 2013, : 472 - 478
  • [32] Approximation algorithm for minimum power partial multi-coverage in wireless sensor networks
    Ran, Yingli
    Huang, Xiaohui
    Zhang, Zhao
    Du, Ding-Zhu
    JOURNAL OF GLOBAL OPTIMIZATION, 2021, 80 (03) : 661 - 677
  • [33] Approximation algorithm for minimum power partial multi-coverage in wireless sensor networks
    Yingli Ran
    Xiaohui Huang
    Zhao Zhang
    Ding-Zhu Du
    Journal of Global Optimization, 2021, 80 : 661 - 677
  • [34] An Iterative Rounding 2-approximation Algorithm for the k-partial Vertex Cover Problem
    Jian-hua TU
    Jun-feng DU
    Feng-mei YANG
    Acta Mathematicae Applicatae Sinica, 2014, (02) : 271 - 278
  • [35] An iterative rounding 2-approximation algorithm for the k-partial vertex cover problem
    Jian-hua Tu
    Jun-feng Du
    Feng-mei Yang
    Acta Mathematicae Applicatae Sinica, English Series, 2014, 30 : 271 - 278
  • [36] An Iterative Rounding 2-approximation Algorithm for the k-partial Vertex Cover Problem
    Tu, Jian-hua
    Du, Jun-feng
    Yang, Feng-mei
    ACTA MATHEMATICAE APPLICATAE SINICA-ENGLISH SERIES, 2014, 30 (02): : 271 - 278
  • [37] A primal-dual approximation algorithm for the k-prize-collecting minimum power cover problem
    Liu, Xiaofei
    Li, Weidong
    Xie, Runtao
    OPTIMIZATION LETTERS, 2022, 16 (08) : 2373 - 2385
  • [38] A primal-dual approximation algorithm for the k-prize-collecting minimum power cover problem
    Xiaofei Liu
    Weidong Li
    Runtao Xie
    Optimization Letters, 2022, 16 : 2373 - 2385
  • [39] Vertex Cover Problem-Revised Approximation Algorithm
    Shah, Kartik
    Reddy, Praveenkumar
    Selvakumar, R.
    ARTIFICIAL INTELLIGENCE AND EVOLUTIONARY ALGORITHMS IN ENGINEERING SYSTEMS, VOL 1, 2015, 324 : 9 - 16
  • [40] A faster, better approximation algorithm for the minimum latency problem
    Archer, Aaron
    Levin, Asaf
    Williamson, David P.
    SIAM JOURNAL ON COMPUTING, 2008, 37 (05) : 1472 - 1498
12345