【摘 要】
：
在本文中，我们将考虑如下三个在网络设计中抽象出来的优化问题，一是内点带权最小生成树问题，二是多商品设备选址问题，三是多层次设备选址问题。本文中考虑的这三个问题的若干版本
论文部分内容阅读
在本文中，我们将考虑如下三个在网络设计中抽象出来的优化问题，一是内点带权最小生成树问题，二是多商品设备选址问题，三是多层次设备选址问题。本文中考虑的这三个问题的若干版本均是NP难的，因此本文对这三个问题的近似性的上界和下界做了系统的研究。我们证明了在度量空间中内点带权生成树问题是NP-hard的，并给出了两个在度量空间下的近似算法，分别达到了3.52和3.106的近似度，同时证明了问题是难以有小于1.463的近似度的，除非NP DT1ME[n]。在一般空间下，我们也给出了两个近似算法，分别达到了2.35lnn和2H<,n>的近似度，其中Hn=Σ<,i=1>1/i，同时证明了对任意ε>0，问题是难以有小于(1-ε)H<,n>的近似度的，除非NP DTIME[n]。对多商品设备选址问题，我们给出了O(lnn)近似度的算法。对多层次设备选址问题，我们的算法能达到lnn的近似度，如果k是设备的层次数。
本文中，在这三个问题的很多版本的近似算法中，我们都使用了我们近似集合覆盖问题的贪心算法。这个贪心算法尽管概念上简单，但在有些问题中具体使用起来却并不容易。本文选取的这三个问题的几个近似算法是集合覆盖贪心算法相同的框架在近似不同问题时使用方法不同的非常好的例子。
其他文献
本论文所反映的研究工作的项目背景是四川省网络通信技术重点实验室与核工业部九院的合作预研项目“无人驾驶机群作战网络体系结构研究”。无人驾驶机群作战网络是一类特殊的
在信息技术飞速发展的今天,信息安全显示出前所未有的重要性。电子商务、电子银行、网络安全等应用领域更是急需高效的自动身份认证技术,生物特征识别技术以其特有的稳定性、
计算机支持的协同设计是并行工程的重要组成部分，是21世纪的生产模式，其重要性在于使不同地点的设计人员、施工人员和用户能同步或异步地参与协作设计工作，从而加快设计进度和提
随着Internet技术和网络业务的飞速发展，用户对网络资源的需求空前增长，网络也变得越来越复杂。越来越多的网络应用程序需要了解网络延迟、带宽、吞吐率等网络性能参数，以支持不
网络技术的迅速发展和J2EE平台的广泛应用，基于B／S的多层WEB体系结构逐渐发展起来，多层WEB应用的开发已经成为主流。但是，多层WEB体系结构的设计中，仍然存在程序可重用度低、维护
儿童计划免疫工作手续繁琐，工作量大，不易及时汇总分析。现在全国有不少地方在进行信息化建设来解决上述问题。由于经济条件、网络覆盖等因素影响，目前的儿童计划免疫大多使用单
在没有软件源代码的情况下，为了对其增加功能或修正错误，需要在机器指令级别上对软件进行修改，将机器代码嵌入到宿主软件中。这就是软件或代码嵌入。软件嵌入由来已久，文件补丁、
当今，人类已经进入了网络时代。然而，人们在得益于信息革命带来的巨大机遇的同时，也不得不面对信息安全问题的严峻考验。入侵检测技术作为确保计算机网络信息安全的一个重要手段
随着信息技术的迅速发展，网络信息不断膨胀。如何让网络信息更好地为人类服务，已成为未来几年的一个研究热点。一方面是人们对快速、准确而全面获取信息的渴望，而另一方面却是网
计算机作为互联网的一种重要信息终端，是目前人们获取网络信息的主要工具。然而，由于传统的上网方式限制了上网人数，互联网的访问模式逐渐从单一访问方式向多种用户终端发展。近