【摘 要】
：
集合覆盖问题是组合优化领域中的经典问题,它指的是在给定的集族中选一个阶数最小子集族来覆盖所有给定的元素.该问题不仅具有很高的理论价值,随着无线网络的发展更具有了越
论文部分内容阅读
集合覆盖问题是组合优化领域中的经典问题,它指的是在给定的集族中选一个阶数最小子集族来覆盖所有给定的元素.该问题不仅具有很高的理论价值,随着无线网络的发展更具有了越来越广泛的应用背景.本文主要研究的是集合覆盖的两种变形:最小赋权部分连通集合覆盖问题(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-路点覆盖.本文考虑的是在线3-路点覆盖模型:图G的信息,它通过逐点显现的方式呈现出来,当一个新的点出现时,我们必须做出决策,判断它是否需要被选入C中.我们给出了一个自然的算法,其近似比不会超过图G的最大度△,并给出了该近似比的紧例子.
其他文献
伴随着经济的快速发展,我国上市公司财务舞弊问题日渐凸显出来。这不仅影响到投资者的信心和热情,也扰乱了资本市场的正常运行。因此对上市公司财务报告舞弊行为的研究就显得
随着多核处理器的发展,多线程编程在提高软件服务质量方面扮演了愈发重要的角色。循环结构在蕴含了丰富并行性的同时,因自身的复杂性及多样性,成为软件执行过程中最耗时的部
目的:以人乳腺癌MCF-7细胞及其耐阿霉素MCF-7/ADM细胞为模型,研究姜黄素介导的光动力疗法诱导肿瘤细胞凋亡及其凋亡机制,并探讨姜黄素酸敏感脂质体联合光动力疗法的体外抗肿瘤活性。为姜黄素介导的光动力疗法的临床应用提供基础研究,同时为克服肿瘤多药耐药提供一定的依据和思路。方法:1.采用高效液相色谱法对姜黄素进行分析方法学考察和验证,为后续实验提供分析基础。2.采用MTT法考察姜黄素介导的光动力
<正>作为工程机械方面的一项重要系统,其远程监控系统在近期得到了长足的发展。该项课题的研究,将会更好地提升其实践水平,从而有效保证工程机械远程监控系统的良好效果。本
由于交通事故中侧滚翻事故的死亡率非常高，为达到车辆发生侧翻时对乘员的保护，充分考虑我国国情，2011年1月14日，我国正式发布GB26134--2010《乘用车项部抗压强度》国家强制性标准
三峡地区是中国文化版图上重要的文化地理空间,相关于本地区的文学现象诸如某些文学原型与母题的生成、三峡本土作家的孕育、外来作家在这一地区的经行与吟咏、驻足其间的历
<正> 山东是我国中生代陆相地层重要的分布地区之一,著名的地层名称如蒙阴组、莱阳组、青山组、王氏组等,都在这里。这些地层所含植物、瓣鳃类、腹足类、昆虫、叶肢介、鱼、
目的探讨血清脂蛋白相关磷脂酶A2(lipoprotein-associated phospholipase A2,Lp-PLA2)、几丁质酶-3样蛋白-1(chtinase-3-like-1 protein,YKL-40)与2型糖尿病不同程度视网膜病
语文作文是高考试卷中分值最大的一道试题,是高考考试内容改革的重点。恢复高考以来,高考作文题型历经标题、话题和材料作文的发展,并形成评价的标准。《国务院关于深化考试
编者按：世界音乐（World music）又称民族流行音乐（Ethno pop），可泛指世界上所有的民族音乐，它是民族音乐走向国际音乐市场后形成的一种音乐类型。从朱哲琴到萨顶顶再到如今的杭盖、帕