两个分批排序问题的NP-完备性证明

讨论了单台与两台批处理机上的、目标函数均为加权总完工时间的分批排序问题.用整数背包问题具体证明了这两个问题的NP-完备性.

基于NP-完备理论的组合最优化及计算复杂性研究

近年来,我国计算机科学得到了迅猛的发展,这也使人们提出许多理论试图深入揭示NP-完备理论所具备的密切关系,对基于NP-完备理论进行研究,将有助于推动计算机科学、运筹学、离散数学等相关学科的发展,进而帮助人们更好地利用NP-完备理论来处理实际问题。鉴于此,本文对基于NP-完备理论的组合最优化及计算复杂性进行深入的研究,以期能够为NP-完备理论的研究有一定贡献。

四正则图的分离问题是NP-完备的(英文)

本 文证明了 四正则图 的最小平 分问题是 Ｎ Ｐ完备的 ，因而可得 到四正 则图的最 小 α分离问 题也是 Ｎ Ｐ完备

矩形件排样优化的一种近似算法

本文对理论上属于ＮＰ－完备问题的二维矩形件优化排样问题，构造了一个效率高、速度快、可令人满意的一种近似算法。该算法的主要思想是在排样过程中根据一种局部最优原则不断地动态产生一些较小的矩形，然后对这些小矩形区域排样，同时也消去一些已排过的矩形区域，直至所有的矩形件被排完。根据本文算法我们开发了一个矩形件排样系统。

复制法及其在分批排序问题中的应用

首次提出分批排序问题中的复制法,并用其证明了分批排序中的极小化求和问题以及极小化极大问题的NP＿完备性.

小直径图的导出匹配覆盖(英文)

设G是一个图,而M_1,M_2,…,M_k是G的k个导出匹配.称{M_1,M_2,…,M_k)是图G的一个k-导出匹配覆盖,若V(M_1)∪V(M_2)∪…∪V(M_k)=V(G).k-导出匹配覆盖问题是指对任一个给定的图G是否存在一个k-导出匹配覆盖.这篇文章证明了:直径为6的图的2-导出匹配覆盖问题和直径为2的图的3-导出匹配覆盖问题是NP-完备的,直径为2的图的2-导出匹配覆盖问题多项式可解.

多重群体遗传算法在装箱问题中的应用研究

装箱问题是一个有很强应用背景的组合优化问题,求解极为困难。为有效解决该问题,提出了多重群体遗传算法,给出了具体的遗传算法步骤。在算法中采用新陈代谢的选择策略,以更好地保持进化过程中的遗传多样性。实践表明,引入多重群体遗传算法后,装箱效率有明显的改善和提高。

组合最优化与计算复杂性综述

综合论述了组合最优化理论与计算复杂性理论,尤其是NP-完备理论之间的密切关系,揭示出NP-完备理论研究的重大理论和现实意义。

一类双约束最短路问题的近似算法

带时间和边数约束的双约束最短路问题是NP 完备的 .它的一种拟多项式精确算法可以利用动态规划方法给出 ,在此基础上采用rounding和scaling的处理技术得到了一种全多项式时间近似方案 (FPAS) .

基于有向图的装箱问题的算法研究

本文基于经典一维装箱问题进行深入研究.首先将装箱问题与有向图相结合,研究了无有向圈的有向图上的装箱问题以及基础圈有向图上的装箱问题,同时对这两个问题设计了相应的近似算法;其次,深化研究成果,将装箱问题同染色问题相结合,研究了无有向圈的有向图上的染色装箱问题以及基础圈有向图上的染色装箱问题,并对这两个问题分别设计了相应的近似算法和启发式算法.

带学习效应的极小化全总完工时间的分批排序问题

讨论了分批排序中工件具有带学习效应、目标函数为极小化加权总完工时间两个问题,分别就所有工件的加工时间都相等的情况给出了两个算法,并证明了这两个算法的最优性。

具有稳定性约束的一维箱子覆盖问题

给定一个物品序列和若干箱子,如何合理地放置物品以使得最多的箱子被覆盖就称为箱子覆盖问题。作为一维箱子覆盖问题的推广,提出了具有稳定性约束的一维箱子覆盖问题,即要求同一箱子中小的物品置于大的物品上方。分析了问题的NP-完备性,给出了一种弱渐进近似算法,并分析了算法的时间复杂度。

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

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

装箱问题的一种新的近似算法

研究了一维装箱问题 (BinPackingProblem) ,给出了一个新的近似算法 :交叉装填算法 (简称CF算法 ) .证明了CF算法达到装箱问题的最好的近似值 32 ;并且当这些物件的大小按非增性质预先排序后 。

最小基数箱子覆盖问题及其启发式算法

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

执行时间可变的任务在多处理机上的排序问题

研究一类有实际价值的网页下载问题,把其抽象成一类有n项独立任务在m台不同处理机上执行的排序问题,这里,每项任务在不同处理机上可以有不同起始时间和不同的执行时间.文章指出该问题是强NP-完备的,该问题在特殊情形下能够转化为图论中的最大匹配问题,从而给出了在此情形下的一个完全解决方案.

信息传播的最优结构

研究连通网络中的信息传播问题 ,即有信息的节点vi在每个单位时间里能同时向它的至多ki(ki ≥1)个邻点发送信息 ,要求传播的最短时间 ,使得网络中所有顶点均有此种信息 .鉴于在任意网络中该问题是NP-完备的 ,特研究一种特殊的网络 ,即m维立方体网络 .通过应用递推技巧 ,揭示了在m维立方体网络上信息传播的诸多好的特性及有趣的现象 。