A new DNA algorithm to solve graph coloring problem

Using a small quantity of DNA molecules and little experimental time to solve complex problems successfully is a goal of DNA computing. Some NP-hard problems have been solved by DNA computing with lower time complexity than conventional computing. However, this advantage often brings higher space complexity and needs a large number of DNA encoding molecules. One example is graph coloring problem. Current DNA algorithms need exponentially increasing DNA encoding strands with the growing of problem size. Here we propose a new DNA algorithm of graph coloring problem based on the proof of four-color theorem. This algorithm has good properties of needing a relatively small number of operations in polynomial time and needing a small number of DNA encoding molecules (we need only 6R DNA encoding molecules if the number of regions in a graph is R).     

一种求解JOB SHOP问题的多向交叉遗传算法

针对传统的遗传算法在交叉算子设计上的不足,提出一种多向交叉的方法,本方法在产生子代的过程中具有保持个体多样性、克服早熟以及泛化能力强等优势。本文以一个具体的JOB SHOP问题作为例子来说明它的优势。     

大型企业库存管理中的数学模型——转库流向优化及时间推荐

在供应—生产—销售的供销环节中 ,大型企业的出厂决策问题是非常重要和难解决的。本文以某钢铁厂出厂决策支持系统为背景 ,对其中业务管理中的库存管理建立起数学模型体系。分析了模型的特点 ,由于 0— 1归划为 NP—难问题 ( NP—完全问题 )及一些问题属于大规模资源优化问题 ,当问题规模增大时求解变得极其困难。针对这些问题的特点介绍了求解模型的算法 :现有程序包、启发式算法和线性规划与启发混合的算法。这些算法在应用中取得了较好的效果。     

社交网络中求最小正影响支配集的改进算法

网络中求解最小正影响支配集的问题已经被证明是NP难问题,且已有性能较好的贪心求解算法．通过分析现有的贪心近似算法（Wang-Greedy）和贪心启发式算法(Raei-Greedy),融合其贪心策略,提出了1个改进的贪心近似算法(Hybrid-Greedy)．理论分析表明,Hybrid-Greedy仍保持Wang-Greedy的近似比性能和时间复杂度．在一些较大规模的真实社交网络实例中的实验研究表明,Hybrid-Greedy在这些社交网络中所得解的质量较Wang-Greedy和Raei-Greedy有明显提高．     

超图嵌入图的最小拥挤问题展望

We consider the problem of embedding hyperedges of a hypergraph as paths in a cycle such that the maximum congestion,the maximum number of paths that use any single edge in a cycle,is minimized. The Minimum Congestion Hypergraph Embedding in a Cycle problem is known to be NP-hard and its graph version,the Minimum Congestion Graph Embedding in a Cycle,is solvable in polynomial time. Furthermore,for the graph problem,a polynomial time approxima-tion scheme for the weighted version is known. For the hypergraphmodel, several approximation algorithms with a ratio of two have been previously published. A recent works on this problem reduced the approximation ratio to 1.5. We present a polynomial time approximation scheme in this paper,settling the debate regarding if the problem is polynomial time approximable     

A new DNA algorithm to solve graph coloring problem

Using a small quantity of DNA molecules and little experimental time to solve complex problems successfully is a goal of DNA computing. Some NP-hard problems have been solved by DNA computing with lower time complexity than conventional computing. However, this advantage often brings higher space complexity and needs a large number of DNA encoding molecules. One example is graph coloring problem. Current DNA algorithms need exponentially increasing DNA encoding strands with the growing of problem size. Here we propose a new DNA algorithm of graph coloring problem based on the proof of four-color theorem. This algorithm has good properties of needing a relatively small number of operations in polynomial time and needing a small number of DNA encoding molecules (we need only 6R DNA encoding molecules if the number of regions in a graph is R).     

一类优化问题中的不变决策子集

对一类优化问题--背包问题(0-1Knapsack Problem)的求解过程进行了分析,得到了不变决策变量集合,为化简对问题求解的算法奠定了数学基础.     

物种保护投资地点方案选择的优化

讨论了在有限资金的情况下，为了保证生物的多样性，如何进行投资将获得最佳的收益．提出了绝对优势模型，这个规划是非线性的0-1规划且是NP难的．为了简化计算，将其近似为线性规划即线性化的绝对优势模型，并应用软件解这个规划．比较了这个近似与对原模型用穷举法解决在计算上的优势．分析得出的结果，并对其应用进行了讨论．     

Hamming距离下的最短路逆问题

针对Hamming距离下的最短路逆问题,分析了最优解的性质,给出并证明了问题存在可行解的充分必要条件;利用把背包问题的实例多项式归约到该问题的实例,证明了该问题为NP困难的,为设计该类问题的近似算法提供了理论依据.     

Kernelization in Parameterized Computation： A Survey

Parameterized computation is a new method dealing with NP-hard problems, which has attracted a lot of attentions in theoretical computer science. As a practical preprocessing method for NP-hard problems, kernelizaiton in parameterized computation has recently become an active research area. In this paper, we discuss several kernelizaiton techniques, such as crown decomposition, planar graph vertex partition, randomized methods, and kernel lower bounds, which have been used widely in the kernelization of many hard problems.