摘要
在近似算法领域,集合覆盖(SetCover)是研究的比较早和比较透彻的问题之一.该文提出了一类与集合覆盖很相似的问题:集合击中和弱集合b覆盖,并且给出了解决它们的近似算法,还证明了它们的不可近似性.
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.
出处
《计算机学报》
EI
CSCD
北大核心
2005年第9期1497-1500,共4页
Chinese Journal of Computers
基金
国家自然科学基金(60273045
60496321
60373021)
科学技术部基础研前期研究专项基金(2001CCA0300)
上海市科技发展基金(03JC14014)资助
