连通3-路点覆盖问题及部分集合多重覆盖问题的近似算法

摘要

覆盖问题是一类非常著名的组合优化问题.顶点覆盖问题与集合覆盖问题，作为图灵奖获得者Richard M.Karp提出的21个经典NP完全问题中的两个备受关注的问题，目前已被理论计算机科学领域中的广大研究工作者所熟知，因而相关的研究工作已经有很多.本文主要是研究这两类问题所对应的推广问题连通k-路覆盖问题(CVCPk)与部分集合多重覆盖问题(PSMC).
　　连通k-路点覆盖问题(CVCPk)产生于无线传感网络中的安全与检测.对于一个图G=(V,E)，如果图中的每一条k-1长路都有至少一个点属于点集S，我们称点集S是图G的k-路点覆盖，如果S在图G中导出的子图是连通的，我们就称点集S是图G的连通k-路点覆盖（CVCPk）.
　　部分集合多重覆盖问题(PSMC)是集合多重覆盖问题(SMC)与部分集合覆盖问题(PSC)的结合.给定一个集合E，实数0＜ρ＜1，以及由E的子集构成的集簇S.对于任意集合S∈S都给定一个成本ws＞0.对于任意元素e∈E都定义一个覆盖需求re＞0.集合多重覆盖问题指的是找到一个最小的子集簇F(∈)S，使得E中的每一个元素都能达到覆盖要求，其中元素e能达到覆盖要求指的是e属于F的至少re个集合.部分集合多重覆盖问题指的是找到一个最小的子集簇F'(∈)S，使得E中至少ρ|E|个元素达到覆盖要求值.
　　本学位论文计划分为四章，第一章介绍相关概念与背景知识，并介绍研究现状.第二章，设计了一个连通3-路覆盖问题的近似算法，其近似比为2α+1/2，其中α为（不加连通条件的）3-路覆盖问题的近似比.第三章给出部分集合多重覆盖的贪婪算法，并提出一个新的衡量算法性能的参数:部分完全近似比，即将部分覆盖的近似值与完全覆盖的最优值进行比较.结果表明我们的算法部分完全近似比为lnr/1-p，数值实验也表明了用部分覆盖替代完全覆盖的优点.第四章对研究方法与研究结果进行讨论与总结.

目录

摘要

第一章导言

1．1定义及术语

1．2研究的问题和结果

1．2．1 连通3-路点覆盖问题

1．2．2 部分集合多重覆盖问题

第二章连通3-路点覆盖问题

2．1相关背景知识

2．2 近似算法

2．3 算法分析

第三章部分集合多重覆盖问题的近似算法Versus集合多重覆盖

3．1 算法

3．2 算法的部分完全近似比分析

3．3 紧例子

3．4 关于结果的一些讨论

第四章讨论与总结

参考文献

攻读学位期间取得的研究成果

致谢

声明