一类弱集合覆盖问题的近似算法

• 作者: 张涌 朱洪
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: 集合击中 弱集合b-覆盖 NP难 近似算法
• 年，卷（期）: 2005,（9）
• 所属期刊栏目: 研究论文与技术报告
• 页码范围: 1497-1500
• 页数: 4页
• 分类号: TP301
• 字数: 3538字
• 语种: 中文
• DOI: 10.3321/j.issn:0254-4164.2005.09.010

摘要

在近似算法领域,集合覆盖(Set Cover)是研究的比较早和比较透彻的问题之一.该文提出了一类与集合覆盖很相似的问题:集合击中和弱集合b -覆盖,并且给出了解决它们的近似算法,还证明了它们的不可近似性.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	张涌	复旦大学计算机科学与工程系智能信息处理实验室	9	416	7.0	9.0
2	朱洪	复旦大学计算机科学与工程系智能信息处理实验室	29	159	7.0	12.0