求解k（〈n）-中心问题的快速算法

来源 :计算机研究与发展 | 被引量 : 0次 | 上传用户：asas123456123456

【摘要】

：

提出求解k(＜n)-中心问题的两类算法,其中第1类算法适用于k＜10的情况,而第2类算法可应用于10＜k＜n的情况 .两类算法的思想不同,前者利用等分凸壳直径的方法并且所确定的圆的圆心位

【作者】

：

周培德

【机构】

：

北京理工大学计算机工程与科学系

【出处】

：

计算机研究与发展

【发表日期】

：

2004年4期

【关键词】

：

k-中心问题凸壳算法时间复杂性 kcenter problem convex hull algorithm time complexity

下载到本地 , 更方便阅读

下载此文赞助VIP

声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架

论文部分内容阅读

提出求解k(＜n)-中心问题的两类算法,其中第1类算法适用于k＜10的情况,而第2类算法可应用于10＜k＜n的情况 .两类算法的思想不同,前者利用等分凸壳直径的方法并且所确定的圆的圆心位置是固定的,而后者采用多种参数随机化的方法,从而圆心是不确定的 .此外证明了算法的正确性并且分析了算法的复杂性 .

其他文献

周期多帧任务的固定优先级调度算法的调度分析

实时操作系统的核心问题——实时任务的调度是实时系统研究的重点之一.主要讨论了周期多帧任务的固定优先级调度算法的调度情况，证明了对于周期多帧任务DM算法不是最优的，同时

期刊

周期多帧任务固定优先级调度算法实时操作系统调度分析realtime critical instant zone periodic multifram

构件化领域框架设计与实现

文中介绍了由东北大学软件中心研究的构件化领域框架系统ＮＥＳＣ。它以构件技术、软件体系结构技术和应用软件开发技术为基础，采用了界面、规则和存储的层次化结构，实现了规则控制、时

期刊

软件构件软件体系结构领域框架软件开发software component software architecture domain specific

多Agent系统中基于Rough集的推理

定义了多Ａｇｅｎｔ系统中的推理模型，建立了在该模型下的Ｒｏｕｇｈ集和基于Ｒｏｕｇｈ信方法的Ｒｏｕｇｈ包含计算或称集合连接计算，在知识发现和数据挖掘中，集合之间往往不是给出它们的相等性，而是讨论它们之间的Ｒｏｕｇｈ包含或

期刊

多AGENT系统ROUGH集推理模型人工智能multiagent system rough set rough inclusion calculus

一种基于颜色的图像表示及全局相似检索技术

基于内容的图像检索是当前图像数据库领域中的一个研究热点 .给出了一种描述图像视觉特征的图像表示方法 ,并据此计算图像之间的全局相似度 .首先 ,通过对彩色空间的分析 ,提取图像中的颜色不变量 ,然后在频域内对这样的颜色信息进行分析 .对频域分析的结果进行 K- L变换 ,变换后的低维向量即为图像的颜色表示 .在此基础上 ,也讨论了图像的相似度量以及相应的图像检索技术 ,并给出了实验结果和图像检索性

期刊

图像数据库图像表示全局相似检索图像处理计算机image database image representation and retrieval c

DHT抖动处理代价的分析

DHT(分布式Hash表)是P2P网络中的一种结构化定位技术.针对DHT很难解决的抖动问题,提出了反向邻居节点数的概念,计算了几种常用的DHT的反向邻居节点数,找出了影响DHT抖动处理

期刊

P2P网络分布式Hash表抖动处理代价反向邻居节点数结构化定位

《计算机研究与发展》2004年（第41卷）总目次

期刊

基于LONWORKS网络的多处理器智能节点设计

在基于ＬＯＮＷＯＲＫＳ网络的现场总线中，Ｎｅｕｒｏｎ芯片是节点的核心，但是其处理能力不足以胜任复杂的计算任务．为增强节点的计算能力，提出并实现了一种非对称多处理器（ＡＭＰ）结构的控制节点设计方案，多个处理器之

期刊

现场总线多处理器LONWORKS网络分布式控制LONWORKSfieldbusmultiprocessordualchannel bussing

新时代背景下开发区宣传工作思路的创新

党的十九大指出，我国已经进入了“新时代”。在这个大背景下，作为以经济建设为主要使命的开发区，宣传工作在品牌塑造、舆论引导、招商引资、社会服务等诸多开发区工作中，发挥着越

期刊

新时代开发区宣传工作创新

一种基于信息增益与费用评价函数的特征选择准则

特征选择问题是机器学习和模式识别中的一个重要问题，然而，在实际应用中，由于没有将特征选择与特征提取过程统一考虑，只注重特征本身的分类性能，没有考虑特征提取的费用问题，导致识

期刊

信息增益费用特征选择机器学习模式识别information gain cost feature selection decision tree

Java监视器的硬件支持及其操作算法

为支持线程间的同步，Ｊａｖａ虚拟机中引入了监视器进入与退出指令，但这会在大部分的Ｊａｖａ程序中产生严重的性能问题，在目前的软件实现方法中，存在内存开销大或性能较低等问题。因此，ｐｉｃｏＪａｖａ内核对监视

期刊

JAVA语言监视器硬件操作算法Java virtual machine thread synchronize monitor lock

求解k（〈n）-中心问题的快速算法

与本文相关的学术论文