| 一类弱集合覆盖问题的近似算法 |
| |
| 引用本文： | 张涌,朱洪.一类弱集合覆盖问题的近似算法[J].计算机学报,2005,28(9):1497-1500. |
| |
| 作者姓名： | 张涌 朱洪 |
| |
| 作者单位： | 复旦大学计算机科学与工程系智能信息处理实验室,上海,200433 |
| |
| 基金项目： | 本课题得到国家自然科学基金（60273045,60496321,60373021）、科学技术部基础研究重大项目前期研究专项基金（2001CCA0300）和上海市科技发展基金（03JC14014）资助. |
| |
| 摘 要： | 在近似算法领域，集合覆盖（Set Cover）是研究的比较早和比较透彻的问题之一．该文提出了一类与集合覆盖很相似的问题：集合击中和弱集合b-覆盖，并且给出了解决它们的近似算法，还证明了它们的不可近似性．
|
| 关 键 词： | 集合击中 弱集合b-覆盖 NP难 近似算法 |
| 收稿时间： | 2003-07-18 |
| 修稿时间： | 2003-07-182005-03-28 |
Approximation Algorithms for the Problems of Weak Set Cover |
| |
| ZHANG Yong,ZHU Hong.Approximation Algorithms for the Problems of Weak Set Cover[J].Chinese Journal of Computers,2005,28(9):1497-1500. |
| |
| Authors: | ZHANG Yong ZHU Hong |
| |
| Abstract: | In the field of approximation algorithms, Set Cover is one of the problems studied profoundly. This paper puts forward Set Hit and Weak Set b-Cover, which similar to the problem of Set Cover, gives approximation algorithms to solve them, and proves their inapproximability. |
| |
| Keywords: | Set Hit Weak Set b-Cover NP-Hard approximation algorithm |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
