三维传感器网络空间结构及其覆盖特性 被引量：3

1

作者 刘华峰 金士尧 《计算机应用》 CSCD 北大核心 2007年第4期909-912,共4页

三维传感器网络在现实世界中的空间结构远远复杂于二维传感器网络。当前大多数研究采用的随机空间结构假设,不能完全代表三维传感器网络的实际需求。因此提出三种空间对称的立方格结构传感器网络,并利用空间镶嵌理论分析其覆盖特性。同... 三维传感器网络在现实世界中的空间结构远远复杂于二维传感器网络。当前大多数研究采用的随机空间结构假设,不能完全代表三维传感器网络的实际需求。因此提出三种空间对称的立方格结构传感器网络,并利用空间镶嵌理论分析其覆盖特性。同时,针对现有随机结构无线网络中相变现象的分析工具复杂的问题,采用箱覆盖技术推导了随机结构三维传感器网络的临界覆盖半径。 展开更多

关键词 三维传感器网络 立方格 空间镶嵌 箱覆盖

下载PDF 职称材料

染色的装箱问题及其近似算法 被引量：1

2

作者 孙春玲 《云南民族大学学报（自然科学版）》 CAS 2005年第3期210-212,共3页

给出了染色装箱问题和染色覆盖问题的数学描述,得到了给定颜色限制的染色装箱问题和染色覆盖问题的两个近似算法.

关键词 装箱问题 染色 近似算法

下载PDF 职称材料

基于LIB的有色箱覆盖问题

3

作者 杨鼎强 《计算机工程与设计》 CSCD 北大核心 2008年第9期2269-2271,共3页

提出了如下定义的受位置约束的有色箱覆盖问题,即在有色物品的箱覆盖过程中,要求重(长)的物品置于轻(短)的物品下方。该问题是一个新的组合优化问题,来源于多处理器任务调度。给出一个求解该问题的局内近似算法KC-LIBFF算法,分析其最坏... 提出了如下定义的受位置约束的有色箱覆盖问题,即在有色物品的箱覆盖过程中,要求重(长)的物品置于轻(短)的物品下方。该问题是一个新的组合优化问题,来源于多处理器任务调度。给出一个求解该问题的局内近似算法KC-LIBFF算法,分析其最坏情况渐进性能比为0,并给出了相应的实验结果;进一步对求解该问题的局内算法性能比的下界进行了讨论。 展开更多

关键词 箱覆盖问题 调度问题 组合优化 近似算法 最坏情况渐进性能比

下载PDF 职称材料

最小基数箱子覆盖问题及其启发式算法 被引量：3

4

作者 孙春玲 李建平 《云南大学学报（自然科学版）》 CAS CSCD 2004年第B07期8-11,共4页

研究了一个新颖的装箱问题,即最小基数箱子覆盖问题(MinimumCardinalityBinCoveringProblem),证明了该问题是强NP-完备的;在物件大小满足一定的条件下,给出了一个时间复杂度为O(n)的启发式算.

关键词 最小基数箱子覆盖问题 强NP-完备 启发式算法 最优值

原文传递

带参在线箱覆盖问题(英文)

5

作者 张国川 《运筹学学报》 CSCD 1999年第2期57-60,共4页

我们考虑在线箱覆盖问题，其中所有被装元素的尺寸不超过1／k（k是正整数）．我们给出了该问题的紧上界并证明简单算法NextFit即是最好的．这个结果推广了Csirik与Totik1988年的工作．最后，我们还给出了二维情形的一个非平凡的上界．

关键词 箱覆盖 在线算法 最坏情形分析

下载PDF 职称材料

最小基数箱子覆盖问题

6

作者 屈红文 《河南教育学院学报（自然科学版）》 2009年第4期1-2,共2页

最小基数箱子覆盖问题,是在物件大小满足一定的条件下的装箱问题.给出了一个时间复杂度为O(n)的启发式算法.

关键词 装箱问题 启发式算法 覆盖

下载PDF 职称材料

箱覆盖问题的半定松驰算法

7

作者 陈峰 姚恩瑜 《运筹学学报》 CSCD 北大核心 2002年第2期85-96,共12页

箱覆盖问题是NP困难问题中的经典问题,得到了广泛地研究.九十年代以来,半定松驰策略被用来求解组合优化问题,取得了很好的结果[13].本文首次给箱覆盖问题的半定松驰算法.算法的理论分析结果表明它适合于求解大规模的箱覆盖问题.

关键词 半定松驰算法 箱覆盖问题 近似算法 组合优化

下载PDF 职称材料

最小费用箱子覆盖问题及其算法

8

作者 杨鼎强 谢冬青 《湖南大学学报（自然科学版）》 EI CAS CSCD 北大核心 2008年第2期77-79,共3页

提出了一种有实际背景的最小费用箱子覆盖问题──每个物品有长度和费用2个参数.针对局外最小费用箱子覆盖问题,给出了一个求解该问题的最坏情况渐近性能比为1/2算法C-FF1.同时给出了一个求解该问题的局内算法C-FF2,其绝对性能比为1/2,... 提出了一种有实际背景的最小费用箱子覆盖问题──每个物品有长度和费用2个参数.针对局外最小费用箱子覆盖问题,给出了一个求解该问题的最坏情况渐近性能比为1/2算法C-FF1.同时给出了一个求解该问题的局内算法C-FF2,其绝对性能比为1/2,并证明了不存在绝对性能比大于1的算法. 展开更多

关键词 近似算法 箱子覆盖问题 组合优化 渐近性能比

下载PDF 职称材料

一维装箱问题的一个衍生问题——最小基数箱子覆盖问题

9

作者 程凤敏 《四川理工学院学报（自然科学版）》 CAS 2006年第4期96-99,共4页

文章介绍一维装箱问题的一个衍生问题:最小基数箱子覆盖问题和它的一个启发式算法。

关键词 衍生问题 箱子覆盖问题 启发式算法 NP-完备性

下载PDF 职称材料

互联网信息管理中的带拒绝装箱覆盖问题

10

作者 杨鼎强 王晨 《计算机工程与设计》 CSCD 北大核心 2007年第10期2453-2454,2457,共3页

作为对装箱覆盖问题的推广,提出了带拒绝的装箱覆盖问题:设有许多等长的一维箱子,给定一个物品集,每个物品有两个参数:长度和费用。物品可以放入箱子也可被拒绝放入箱子。每个物品只准放入一只箱子中,每只箱子中的物品容量总和至少为箱... 作为对装箱覆盖问题的推广,提出了带拒绝的装箱覆盖问题:设有许多等长的一维箱子,给定一个物品集,每个物品有两个参数:长度和费用。物品可以放入箱子也可被拒绝放入箱子。每个物品只准放入一只箱子中,每只箱子中的物品容量总和至少为箱子容量,一旦箱子中的物品长度达到要求则需启用新箱。如果物品被放入箱中,则产生费用。该问题是一个新的组合优化问题,在内部互联网信息管理等问题中有着广泛的应用背景。给出了一个求解该问题的局外近似算法C-FF,分析其最坏情况渐进性能比为1/2,并给出了相应的实验结果。 展开更多

关键词 装箱覆盖问题 近似算法 最坏情况渐进性能比 因特网通信 信息管理

下载PDF 职称材料

带拒绝箱覆盖问题的局内算法

11

作者 杨鼎强 蒋加伏 《计算技术与自动化》 2007年第2期31-33,共3页

作为对装箱覆盖问题的推广,提出带拒绝的装箱覆盖问题。设有许多等长的一维箱子,给定一个物品集,每个物品有两个参数:长度和费用。物品可以放入箱子也可被拒绝放入箱子,每个物品只准放入一只箱子中,每只箱子中的物品容量总和至少为箱子... 作为对装箱覆盖问题的推广,提出带拒绝的装箱覆盖问题。设有许多等长的一维箱子,给定一个物品集,每个物品有两个参数:长度和费用。物品可以放入箱子也可被拒绝放入箱子,每个物品只准放入一只箱子中,每只箱子中的物品容量总和至少为箱子容量,一旦箱子中的物品长度达到要求则需启用新箱。如果物品被放入箱中,则产生费用。该问题是一个新的组合优化问题,在内部互联网信息管理等问题中有着广泛的应用背景。给出一个求解该问题的局内近似算法C-FF,分析其最坏情况渐近性能比为1/2,并给出了相应的实验结果。 展开更多

关键词 箱覆盖问题 近似算法 最坏情况渐近性能比 因特网通信 信息管理

下载PDF 职称材料