最小赋权连通集合覆盖问题的近似算法

发布时间：2021-01-07 20:09

　　集合覆盖问题是组合优化领域中的经典问题,它指的是在给定的集族中选一个阶数最小子集族来覆盖所有给定的元素.该问题不仅具有很高的理论价值,随着无线网络的发展更具有了越来越广泛的应用背景.本文主要研究的是集合覆盖的两种变形:最小赋权部分连通集合覆盖问题（MVW PCSC）和在线3-路点覆盖问题（online VCP3）.对于MWPCSC问题,给定元素集合U,集合族S,权函数c:S → Q+,以集合族中集合作为点集的连通图GS,正整数k≤|U|,其目标是找到一个最小权的子集族S’（?）S使得由S’导出的子图连通,且|US∈S’S|≥k.当GS满足任意两个有公共元素的集合在Gs中的跳数（hop distance）不超过r时,这个问题被称为r-hopPCSC.对最小权的1-hopPCSC,我们给出了一个O(ln（m+ n）-近似算法;对最小基数下r-hopPCSC,我们给出了一个O（ln（m + n））-近似算法.和前人的结果比较,我们的方法要简单的多.对于特殊集合覆盖问题——3-路点覆盖,给定图G（V,E）,当图G中的每一条3个点的路至少有一个点在C中时,我们称C是一个3-路点覆盖.本文考虑的是... 

【文章来源】：浙江师范大学浙江省

【文章页数】：44 页

【学位级别】：硕士

【部分图文】：

图４．２：断言２的图示．用黑色的边代替将会导出一个更大的３－路匹配．??

图４．３：断言３．?１．的证明图示??

厕匪??⑷?（ｂ）??图４．３：断言３．?１．的证明图示??断言３．２．?Ｉｆ?Ｐ?ｅ?Ｍｉ，那么Ｘ?△?－?２，?Ｐ的硬币能分担到Ｐ＇上．??设尸＇＝．在ｃＰ，?＝?｜ｉ＼＾ｌｕＫ，（＼／（Ｐ）＼Ｃ）｜?＝?△?－?１的假设下，我们推出矛盾．??首先，考虑?＜?是ｎＣ？中的唯一点．如果ｕ?由于％己经有三个邻??点在Ｖ（Ｍ）中（如图４．４⑷），那么丨￣婦，㈨）｜?＜?Ａ－３？结合｜ｉＶＫｌＵｉｒ，（｛ｚ４，４｝）｜?＝??｜」Ｖ／ｓ：ｌＵ／ｌ￡＂＇（＇ｌ’（／：＞）＼（７）｜?＝?Ａ?－?１，可知?（圮）｜?２?２．令为中两点？那??么（＾／＾｛叩仰，１！；丨＋⑴是一个比ｉＵ更大的３－路匹酉己如果??■ｕ?＝?％


本文编号：2963165