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

摘要

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