An approximation algorithm for the partial covering 0-1 integer program

An approximation algorithm for the partial covering 0-1 integer program
复制标题

DOI：
10.1016/j.dam.2017.08.024
复制
发表时间：
2020-03
期刊：
Discret. Appl. Math.
影响因子：
--
通讯作者：
Yotaro Takazawa;S. Mizuno;Tomonari Kitahara
Yotaro Takazawa;S. Mizuno;Tomonari Kitahara
中科院分区：
其他
文献类型：
--
作者：
Yotaro Takazawa;S. Mizuno;Tomonari Kitahara

文献摘要

相似文献

部分覆盖0-1整数规划（PCIP）是覆盖0-1整数规划（CIP）的一个松弛问题，使得某些固定数量的约束条件可能不被满足。这种类型的松弛也讨论了部分集多覆盖问题（PSMCP）和部分集覆盖问题（PSCP）。在本文中，我们提出了一个近似算法PCIP扩展的近似算法PSCP的甘地等人。（2004年）。
The partial covering 0–1 integer program (PCIP) is a relaxed problem of the covering 0–1 integer program (CIP) such that some fixed number of constraints may not be satisfied. This type of relaxation is also discussed in the partial set multi-cover problem (PSMCP) and the partial set cover problem (PSCP). In this paper, we propose an approximation algorithm for PCIP by extending an approximation algorithm for PSCP by Gandhi et al. (2004).