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 条
  • [41] Approximation algorithms for the minimum power cover problem with submodular/linear penalties
    Liu, Xiaofei
    Li, Weidong
    Dai, Han
    THEORETICAL COMPUTER SCIENCE, 2022, 923 : 256 - 270
  • [42] Approximation algorithm for minimum weight connected-k-subgraph cover
    Liu, Pengcheng
    Zhang, Zhao
    Huang, Xiaohui
    THEORETICAL COMPUTER SCIENCE, 2020, 838 (838) : 160 - 167
  • [43] Approximation algorithm for minimum connected 3-path vertex cover
    Liu, Pengcheng
    Zhang, Zhao
    Li, Xianyue
    Wu, Weili
    DISCRETE APPLIED MATHEMATICS, 2020, 287 : 77 - 84
  • [44] An Improved Memetic Algorithm for the Partial Vertex Cover Problem
    Zhou, Yupeng
    Qiu, Changze
    Wang, Yiyuan
    Fan, Mingjie
    Yin, Minghao
    IEEE ACCESS, 2019, 7 : 17389 - 17402
  • [45] Greedy approximation algorithm of minimum cover set in wireless sensor networks
    Lu K.-Z.
    Sun H.-Y.
    Ruan Jian Xue Bao/Journal of Software, 2010, 21 (10): : 2656 - 2665
  • [46] Improved Parallel Algorithm for Minimum Cost Submodular Cover Problem
    Ran, Yingli
    Zhang, Zhao
    Tang, Shaojie
    CONFERENCE ON LEARNING THEORY, VOL 178, 2022, 178
  • [47] A Local 2-Approximation Algorithm for the Vertex Cover Problem
    Astrand, Matti
    Floreen, Patrik
    Polishchuk, Valentin
    Rybicki, Joel
    Suomela, Jukka
    Uitto, Jara
    DISTRIBUTED COMPUTING, PROCEEDINGS, 2009, 5805 : 191 - 205
  • [48] A primal-dual approximation algorithm for the k-prize-collecting minimum vertex cover problem with submodular penalties
    Xiaofei LIU
    Weidong LI
    Jinhua YANG
    Frontiers of Computer Science, 2023, 17 (03) : 128 - 135
  • [49] A primal-dual approximation algorithm for the k-prize-collecting minimum vertex cover problem with submodular penalties
    Liu, Xiaofei
    Li, Weidong
    Yang, Jinhua
    FRONTIERS OF COMPUTER SCIENCE, 2023, 17 (03)
  • [50] An improved approximation algorithm for the minimum common integer partition problem
    Lin, Guohui
    Tong, Weitian
    INFORMATION AND COMPUTATION, 2021, 281
12345