2. 您的位置
3. 首页
4. 期刊论文
5. k-supplier问题的贪婪近似算法

k-supplier问题的贪婪近似算法

来源 :中国计量学院学报 | 被引量 : 0次 | 上传用户：huangxz

【摘 要】

：

给定无向完全图G=(V,E)和正整数k,图G的顶点集V被划分为子集F和子集D=V-F.k-supplier问题主要研究如何寻找F中顶点数不多于k的子集S,使得S中的顶点到D中顶点的最大距离最小.

【作 者】

：

丁哲衡 朱芳 王勤 

【机 构】

：

中国计量学院理学院

【出 处】

：

中国计量学院学报

【发表日期】

：

2012年4期

【关键词】

：

k-supplier问题 贪婪算法 近似算法 k-supplier problem greedy algorithm approximation algorit 

【基金项目】

：

国家自然科学基金资助项目(No.11171316)

下载到本地 , 更方便阅读

下载此文 赞助VIP

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

论文部分内容阅读

给定无向完全图G=(V,E)和正整数k,图G的顶点集V被划分为子集F和子集D=V-F.k-supplier问题主要研究如何寻找F中顶点数不多于k的子集S,使得S中的顶点到D中顶点的最大距离最小.研究了k-supplier问题,得到了一个近似比为3的多项式时间贪婪近似算法,并通过实例验证了该算法的有效性.

其他文献

通用热力对象建模与控制仿真平台设计

系统地介绍了自主开发的复杂可视化仿真平台的构成及其主要核心技术,例如共享内存设计、多编译器嵌入、多进程多任务设计等,并且还介绍了第三方图形开发平台VG以及OPC通信技

期刊

热力系统仿真平台三冲量thermal system simulation platform the three impulses

促进乳酸菌发酵特性的植物激活剂筛选

研究了激活剂对乳酸菌发酵性能的影响．通过实验发现，不同乳酸菌所需的激活剂不同，马铃薯汁作为激活剂可有效缩短2号菌的发酵时间，提高其产酸能力，但对1号菌却没有明显的激活作用．

期刊

乳酸菌激活剂发酵性能lactic acid bacteria promotor fermentaion property

白光LED用BaMgAl_(10)O_(17):Eu~(2+)Mn~(2+)蓝绿荧光粉

采用高温固相法制备出一种Eu2+,Mn2+共掺的蓝绿色荧光粉BaMgAl10O17:Eu2+,Mn2+(BAM:Eu2+,Mn2+),对其进行了X射线衍射分析和光谱特性的测试.研究表明,它的发射光谱为双峰结构,

期刊

白光发光二极管蓝绿荧光粉高温固相法white light emitting diodes blue-green emitting phosphrs h

瞬态热线法导热系数测量的数值模拟

利用有限元方法对瞬态热线法导热系数测量进行了数值模拟，对各种因素如加热功率、热线半径以及实验温度等对测量过程的影响进行了分析，并将模拟得到的温升曲线与实验测量得到的

期刊

导热系数瞬态热线法数值模拟有限元thermal conductivity transient hot method numerical simulat

磺胺二甲嘧啶人工抗原的合成与鉴定

采用重氮化法将磺胺二甲嘧啶（SM2）与牛血清白蛋白（BSA）和卵清蛋白（OVA）交联合成人工抗原SM2-BSA与SM2-OVA,并通过紫外扫描、SDS-PAGE电泳、凝胶层析和红外光谱等方法扫描进一步检测

期刊

磺胺二甲嘧啶人工抗原重氮化牛血清白蛋白卵清白蛋白sulfamethazine artificial antigen diazotization

樟树电信号计量特性表征的植物营养生长信息传导机制

采用自制的双重屏蔽微弱电信号测试系统,对木本植物樟树茎干从外到内的韧皮部、形成层和木质部三层生长信息的电信号进行测试计量分析.樟树信息传递是一种微弱、低频的非平稳

期刊

电信号计量时/频域分析植物生长机制樟树measurement of electric signals analysis on time-frequen

铁基超导体的磁性研究

介绍了超导电性的发展简史及其广阔用途,介绍了铁基超导体的结构分类和物质的磁性分类;以BaFe2As2为例综述了铁基超导体中铁磁和超导共存的研究现状,同时以SmOCoAs为例研究了

期刊

铁基超导体结构磁性iron-based superconductorstructuremagnetic property

第七届中韩质量科学双边国际学术会议在中国计量学院举行

2008年7月4日，由国家自然科学基金委员会、韩国科学与工程基金会、上海质量科学研究院共同主办的第七届中韩质量科学双边国际学术会议，在中国计量学院召开，会议由中国计量学院副

期刊

国家自然科学基金委员会国际学术会议质量学院计量中国双边科学研究院

三聚氰胺人工抗原及多克隆抗体的制备

采用戊二醛法将三聚氰胺(Melamine,MEL)偶联到牛血清白蛋白(BSA)上合成免疫原三聚氰胺-牛血清白蛋白(MEL-BSA).三聚氰胺甲醛树脂法对三聚氰胺衍生化,再偶联到鸡卵清蛋白(OVA)

期刊

三聚氰胺人工抗原多克隆抗体melamine artifical antigen polyclonal antibody

维持渭河健康生命

渭河发源于甘肃省渭源县,于潼关汇入黄河.全河流域面积13.5万km2,在我省境内6.24万km2;干流全河长818 km,在我省境内河长504km.渭河绵延关中腹地,流域集中了全省大约61%的人

期刊

渭河生命健康流域面积灌溉面积经济社会渭源县甘肃省GDP决定性陕西黄河潼关干流