【摘 要】
：
本文首先阐述k-median问题及其相关问题的研究背景,然后介绍两个经典的求解Metric k-median问题的近似算法,之后重点阐述本文所做的主要工作和创新点,讨论一般距离空间下的k-
论文部分内容阅读
本文首先阐述k-median问题及其相关问题的研究背景,然后介绍两个经典的求解Metric k-median问题的近似算法,之后重点阐述本文所做的主要工作和创新点,讨论一般距离空间下的k-median问题,其中的距离不一定满足三角不等式,但保证距离是对称的.设d<,max>/d<,min>表示k-median实例中与客户点邻接的最长边长比最短边长的最大者.首先证明d<,max>/d<,min>≤ω+ε的k-median问题不存在近似度小于1+ω-1/e的多项式时间近似算法,除非NP(包含或等于)DTIME(n),由此可推出Metrick-median问题不可近似到1+2/e,除非NP(包含或等于)DTIME(n).然后给出一般距离空间下k-median问题的一个局部搜索算法,新的分析表明若有d<,max>/d<,min>≤ω,则局部搜索算法的近似度为1+ω-1/2.该结果亦适用于Metrick-median.ω≤5时,局部搜索算法求解Metric k-median的近似度为3,好于现有结果3+2/p[10],多年以来研究者们一直在寻找Metrick-median近似度不超过3的多项式时间近似算法,而本文恰好找到一类Metric k-median问题子问题满足上述条件.最后通过计算机实验进一步研究了k-median局部搜索求解算法的实际计算效果和该算法的改进方法.实验结果表明本文提出的针对一般距离空间下的k-median问题局部搜索算法在运行效率和求解结果方面是令人满意的.
其他文献
目前，Internet和电子商务的发展带动了面向Web的数据挖掘技术的发展。在电子商务中，运用数据挖掘技术对服务器上的日志文件等Web数据进行客户访问信息的Web数据挖掘，根据对客户
随着网络技术的飞速发展，网络的安全性也变得越来越重要。PKI是解决网络安全问题的技术支持手段。基于X．509标准的传统PKI解决了网络安全中的身份认证、数据保密、数据完整、不
本文提出了一个基于语义Web的远程教育系统框架,在这个框架中系统用户对资源的检索、共享以及不同系统之间的互操作都是建立在资源本体的基础之上.为了使用本体来表示教育资
由于当前各个系统都对业务的反应时间提出很高的要求，实时操作系统也得到了广泛的应用。实时操作系统的职能是对运行在其上的各种实时应用提供执行时间的保证，也就是对应用的各
电子检务信息系统是构建于J2EE平台技术的应用系统,以实现检察院网上办案、办公为目的.J2EE本身是一系列规范的集合,涉及诸多技术,除了包括人们熟知的Servlet、JSP之外,还包
高光线是一种交互式评估曲面光顺性的简单反射模型,是由曲面上方某处无限延伸的直线光源产生的,是直线光源在曲面上产生的印迹.这些印迹是曲面上点的子集,这些点处的曲面法向
随着流媒体应用程序在Internet上的广泛应用,预计最近一、二年,连续媒体将超过源服务器上可用数据的50﹪.数字视频的高带宽和实时性要求,必将给互连网的负载带来巨大的变化;单
该课题通过对实时系统的研究,对Linux操作系统的实时性和实时通信系统进行了分析和论述,由此提出一种基于Linux的软实时通信模型,并对其应用和关键技术进行了探讨与实现.实时
发电机故障诊断系统，对电力安全生产起着重要保障作用，同时还具有重大的社会效益和经济效益。故障诊断处理系统作为故障诊断系统中的一个子系统，诊断处理子系统的主要功能包括两个方面：1.对每一个诊断结果进行分级处理；2.为专家系统的实际应用提供故障分类管理、动态实时解释、故障追忆、查询、报表打印、权限设置、在线帮助等功能。在多客户端运行机制的前提下，对作为客户端的诊断处理子系统，本文实现了上述两个方面十余
数据仓库技术起源于对大量数据进行处理的需要，是随着业务应用的需要而产生的。与传统的数据库技术相比，数据仓库为决策分析提供了更好的支持，跳出了传统的联机处理的范畴。因此