NP难相关论文
装箱问题（Bin Packing Problem,BPP）是一类经典的组合优化问题,旨在将一定数量的尺寸相等或不相等的物品无重叠地放置在容器内。其中......
给定一个简单无向图G=（V,E）,图划分问题的目标是找到一种满足特定要求的顶点划分方式。顶点平分问题是图划分问题的一个重要变种问题......
该文提出了具有不同中断时间代价的抢先调度问题(P|ptmn(δ)|C):在抢先调度中,一个任务发生一次中断,其执行时间会增加δ ,δ随任......
本文研究了一个属于图论领域的优化问题，即MaximumSimpleSharing(MSS)问题。MsS问题的目标，是在一个二分无向图上寻找由互不相交的路......
针对一种边权重取值范围为[0,1]的无向带权图,提出在社交网络中有实际应用的概率支配集概念.在图中寻找最少点数的概率支配集称为......
本文讨论了加工时间线性增加的排序问题.在经典排序中工件的加工时间是个不变的量,而在某些实际排序问题中,工件的加工时间是可能......
PERM是一种用来求解基于HP模型的蛋白质折叠问题的高效算法.在介绍PERM算法核心思想的基础上,对影响算法效率的因素做了改进:重新......
在扩展网络或网络拓扑发生变化时，需要用最小的代价重新布置网络监测体系，以保证能收集到所有必需的网络信息．更新网络监测体系包括新......
最长路径问题是著名的NP难问题，在生物信息学等领域中有着重要的应用。参数计算理论产生后，参数化形式的κ-Path问题成了研究的热点......
针对钢铁企业生产前存在不可忽略运输的实际，研究了生产与生产前运输费用协调调度问题．由于钢铁企业被调度的工件体积较大及加工前不......
对单机环境下紧急工作的重调度问题进行了研究．初始调度中工作带有到达时间，目标为最小化初始工作的等待时间和；重调度目标是在初始调......
讨论了在有限资金的情况下，为了保证生物的多样性，如何进行投资将获得最佳的收益．提出了绝对优势模型，这个规划是非线性的0-1规划且是N......
TSP是一个典型的组合优化问题,并且是一个NP难题,其可能的路径总数与城市数目n是成指数型增长的,所以一般很难精确地求出其最优解,......
在近似算法领域,集合覆盖(Set Cover)是研究的比较早和比较透彻的问题之一.该文提出了一类与集合覆盖很相似的问题:集合击中和弱集......
k—CARD问题是在一个无向网络G中寻找一棵k条边的子树，使得这棵树的权和最小。目前有很多启发式算法用来解决这类NP难问题。一般的......
在多对单传输模式下，数据分配是P2P分层流媒体中的核心问题．为了提高请求节点服务质量，同时也为了减少对Root节点带宽的占用，分两种情......
基于多跳的无线传感器网络，越靠近sink的传感器节点因需要转发更多的数据，其能量消耗就越快，从而在sink周围形成了一种称为“能量洞”......
论文描述了解决作业车间调度最短完工时间问题的一种快速有效的启发式算法。该算法基于一种优先指派规则，并利用了往前看的思想。从......
二部图作为一种非常重要的数据结构有很多特殊性质,针对文献[4]中的二部图的所有极大匹配求解算法,给出了反例证明了该算法是错误......
在给定的一个除边有代价外点也有两种代价的图中,要求出一棵点边代价和最小的生成树。这个优化问题具有实际应用背景。证明了该问......
为了找到一种求解工厂作业调度问题的好方法 ,文章首先阐述了拟物法的思想 ,紧接着在此思想上提出了前沿沉底法 ,并根据前沿沉底法......
TSP是一个典型的组合优化问题，并且是一个NP难题，其可能的路径总数与城市数目n是成指数型增长的，所以一般很难精确地求出其最优解，因而......
P2P流媒体是一种性价比良好的流媒体服务体系.由于Peer节点的服务能力有限,在大规模的系统应用中,源服务器的带宽等资源仍可能成为......
分布式网络监测系统能够实时有效地收集网络性能数据，但收集过程受到链路延迟和路由跳数的约束．链路约束的分布式网络监测模型研究如......
社交网络因为其流行性,近些年得到学术界的广泛关注,社交网络影响最大化是社交网络领域中最流行的问题之一.经典的影响最大化问题......
在资源有限的情况下求解维修费用的算法是一个01规划的问题。目前已有的算法有可能得到局部最优,但不能保证得到全局最优。针对这......
为了进一步降低监测穿越行为的无线传感器网络强k-栅栏覆盖的能耗,首先证明了强k-栅栏覆盖最小能耗问题是NP难的,进而提出了一个节......
摘要：定义了实数集分裂问题，通过构造与二分图的最大权问题相应的图形模型，证明了实数集分裂问题是NP难的。 关键词：实数集合 分裂......
定义了实数集分裂问题,并给出了一类特殊的实数集分裂问题。通过构造与二分图的最大权问题相应的图形模型,证明了这种特殊的实数集......
研究了新工件到达锁定初始调度的单机重调度问题。即有一组带有不同释放时间的初始工件已经按照最小化完成时间和的优化目标调度完......
疏散性问题来源于城市公共设施定址、同质组选择等实际应用,是一类具有NP难的组合优化问题。根据目标可分为两大类:基于效率的疏散......
随着计算机技术的不断发展和完善,利用办公自动化排课是高等学校教学管理重要又复杂的管理工作之一。高校排课具有高校学生人数多......
NP难度问题在现实生产和生活中广泛存在,其高效求解有着极其重要的经济价值、科研价值、军事价值,但是,由于NP是否等于P一直是一个......
实际生产中而临着越来越多的组合优化问题,其中不少属于NP-hard问题。遗憾的是,由于NP-hard问题的客观难度,迄今为止尚未设计出能......
提出了一种同时测量IP网络带宽利用率和路径时延的测量模型,能够有效降低网络测量的开销。以顶点覆盖和边覆盖的相关理论为基础,证......
图划分问题是一个NP完全问题，很难在多项式时间内获得一个最优解。为快速获得一个图划分的近似最优解，研究了信息论中的相关知识，设计......
车辆调度问题最早由Dantzig和Ramser在1959年提出,该问题是交通运输管理、智能救灾调度指挥系统、网络作业调度管理系统、现代物流......
基于最大节约原则，寻找可以解释基因型样本的最小单体型集合，提出一个新的单体型推导方法．通过将SAT问题和MAX-3-SAT问题归约到这种基......
提出了一种具有中断时间代价的抢先调度问题(P|ptmn(d)|Cmax):在抢先调度中,一个任务发生一次中断,其总的执行时间会增加一个d.该......
提出了具有不同中断时间代价的抢先调度问题(P|ptmn(δi)|Cmax).该问题在工程任务分配、分布式计算和网络通信等实际问题中有着广......
介绍了遗传算法的基本原理,讨论了遗传算法中有关编码表示和遗传算子(包括选择算子、交叉算子、变异算子)设计等方面的技术.针对TS......
从数据集中学习贝叶斯网络结构是一个NP难问题。针对此问题提出基于遗传算子的人工蜂群算法。首先,将贝叶斯网络结构映射为一种二......
云计算作为一种新兴的IT资源供应模式,近年来得到了快速的发展。云计算旨在低成本地为用户按需提供高质量的弹性云服务,而云服务的......
近些年,随着汽车制造工业的快发展以及私人汽车的大量普及,车联网的研究变得越来越重要并且已经引起了很多研究人员的关注。车联网......
矩阵特征值互补问题在力学系统领域有广泛的应用.在本文中,我们提出了一类特殊的四阶张量特征值互补问题,它是矩阵特征值互补问题......
