最小k-击中集问题的一个随机近似算法

• 作者: 杨智应
• 来源期刊: 计算机应用与软件
• 学科: 工学
• 关键词: 最小k-击中集 贪心算法 随机算法
• 年，卷（期）: 2009,（3）
• 所属期刊栏目: 基金项目论文
• 页码范围: 128-130,133
• 页数: 4页
• 分类号: TP3
• 字数: 3048字
• 语种: 中文
• DOI: 10.3969/j.issn.1000-386X.2009.03.044

摘要

Franco等给出一个基于平均度数的最小3-击中集问题的贪心算法,并给出算法返回击中集规模的上界.首先将其算法推广成为求解最小k-击中集问题的贪心算法HGREEDY1(A,C),并类似地给出算法返回击中集规模的上界;然后给出基于最大度数的贪心算法HGREEDY2(A,C),并证明算法HGREEDY2(A,C)在给定条件下返回的击中集规模上界优于算法HGREEDY1(A,C);另外设计了用于求解最小k-击中集的随机算法RH(A,C),并对其性能进行平均分析;在此基础上设计一个求解最小k-击中集的随机近似算法并讨论其性质.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	杨智应	上海海事大学计算机科学与工程系	29	82	5.0	8.0