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 条
  • [21] Approximation algorithm for the minimum partial connected Roman dominating set problem
    Zhang, Yaoyao
    Zhang, Zhao
    Du, Ding-Zhu
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2024, 47 (04)
  • [22] Approximation Algorithm for the Minimum Connected k-Path Vertex Cover Problem
    Li, Xiaosong
    Zhang, Zhao
    Huang, Xiaohui
    COMBINATORIAL OPTIMIZATION AND APPLICATIONS (COCOA 2014), 2014, 8881 : 764 - 771
  • [23] Approximation to the minimum rooted star cover problem
    Zhao, Wenbo
    Zhang, Peng
    THEORY AND APPLICATIONS OF MODELS OF COMPUTATION, PROCEEDINGS, 2007, 4484 : 670 - +
  • [24] Clever Steady Strategy Algorithm: A simple and efficient approximation algorithm for minimum vertex cover problem
    Fayaz, Muhammad
    Arshad, Shakeel
    2015 13TH INTERNATIONAL CONFERENCE ON FRONTIERS OF INFORMATION TECHNOLOGY (FIT), 2015, : 277 - 282
  • [25] AN IMPROVED APPROXIMATION ALGORITHM FOR THE k-PRIZE-COLLECTING MINIMUM POWER COVER PROBLEM
    Wang, Wencheng
    Cheng, Binhui
    Li, Jianglin
    Chen, Yinhua
    Zhang, Tongquan
    JOURNAL OF INDUSTRIAL AND MANAGEMENT OPTIMIZATION, 2024, 20 (04) : 1703 - 1718
  • [26] New Approximation Algorithms for the Minimum Cycle Cover Problem
    Yu, Wei
    Liu, Zhaohui
    Bao, Xiaoguang
    FRONTIERS IN ALGORITHMICS (FAW 2018), 2018, 10823 : 81 - 95
  • [27] New approximation algorithms for the minimum cycle cover problem
    Yu, Wei
    Liu, Zhaohui
    Bao, Xiaoguang
    THEORETICAL COMPUTER SCIENCE, 2019, 793 : 44 - 58
  • [28] A note on the minimum power partial cover problem on the plane
    Dai, Han
    Deng, Bin
    Li, Weidong
    Liu, Xiaofei
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2022, 44 (02) : 970 - 978
  • [29] A note on the minimum power partial cover problem on the plane
    Han Dai
    Bin Deng
    Weidong Li
    Xiaofei Liu
    Journal of Combinatorial Optimization, 2022, 44 : 970 - 978
  • [30] An Approximation Algorithm for the Minimum Soft Capacitated Disk Multi-coverage Problem
    Dai, Han
    THEORETICAL COMPUTER SCIENCE, NCTCS 2022, 2022, 1693 : 96 - 104
12345