寻求中国货郎担问题最短回路的多项式时间算法

研究求解中国货郎担问题最短回路的多项式时间算法．首先利用计算几何中凸亮与中轴的结构将点集划分成若干个子点集，然后反复采用求子点集凸壳及划分剩余干点集的方法，求得通过于点集的子路径，最后将各子路径连接成一条回路．中国货郎担问题存在多项式时间算法求得最短回路．所设计的算法的时间复杂性为O（n2lbn），将它用于中国货郎担问题，得到一条长度为15404km的最短回路．与陈沐天等人采用几何分块方法所得的最短回路相一致．

一个具有两类工件的多目标排序的多项式时间算法

本文考虑具有两个工件集的单机排序问题。第一个工件集J1以完工时间和为目标函数,第二个工件集J2以最大加权完工时间为目标函数。问题的目标是寻找一种排序,使得两个目标函数的加权和达到最小。本文证明该问题可在O(n1n2(n1+n2))时间内求解。

计算两类网络的可靠性的多项式时间算法

定义了两类有向网络——ＯＲＣ－网络和ＩＲＣ－网络，并且提出一个计算它们的根通信可靠性（网络的一个特定结点（根点）能与其余每个结点通信的概率）的多项式时间算法．对于ＯＲＣ－网络和ＩＲＣ－网络，该算法的时间复杂度分别是Ｏ（｜Ｅ｜）和Ｏ（｜Ｖ｜·｜Ｅ｜），这里，｜Ｖ｜。

约束正定式几何规划的一种多项式时间算法

利用了几何规划的特点 ,借助于对偶及矩阵分析的理论为约束正定式几何规划构造了一种内点算法 ,并证明了算法具有多项式时间收敛性 ,从而推广了张可村等 (1995 )文的结果。

多供应商多零售商经济批量问题的多项式时间算法研究

研究基于多供应商和多零售商构成的经济批量问题,通过构建优化模型,分析订购费用为全部单位数量折扣和增加数量折扣两种情形模型最优解的相关性质.将这些性质应用到动态规划算法设计中,对订购费用为全部单位数量折扣时的一种特殊情形及增加数量折扣的一般情形分别设计了求解问题最优解的多项式时间算法,并用算例说明了算法的执行过程和有效性.

线性分式规划的多项式时间算法

线性规划（ＬＰ）各种形式的多项式时间算法的研究和成果已相当成熟，但对线性分式规划（ＬＦＰ）的研究甚少．在理论上，ＬＦＰ可转换为ＬＰ，但ＬＰ的多项式时间算法求得的多半为近似解，且ＬＦＰ转换为ＬＰ是通过一个非线性分式映射实现的．因此研究和分析ＬＰ的各种多项式时间算法对ＬＦＰ的稳定性具有理论和实际意义．本文首先系统地分析了从ＬＦＰ到ＬＰ的转换及各种性质．然后，将ＬＰ的一些多项式时间算法推广到ＬＦＰ，最后证明它们仍可在多项式时间内求得满足精度的近似解．

一类赋权诱导问题的多项式时间算法

本文介绍了赋权诱导推理的基本概念及其求解算法复杂性研究的现状．诱导推理在人工智能领域有广泛的应用前景，但现有的求解算法都未能从根本上排除ＮＰ－难解性的困扰，本文考虑了其中一类子问题：二阶独立赋权诱导问题，并给出求其最优解的多项式时间算法．本文还对其它诱导问题进行了分析，给出Ｐ问题与ＮＰ问题的分界线．

带有延迟时间下界的k-(n_1,1,…,1)-排序问题的拟多项式时间算法

讨论Wikum的关于带有延迟时间下界的k-(n_1,1,…,1)-链形结构排序问题的拟多项式时间算法,其中当n_1=2的情况已由Yin等人(1999)解决,这里主要以n_1=3的情形为例作更加细致的分析,然后给出较Yin等人(1999)的算法更加有效的拟多项式时间算法.为了保持文章的连续性,也将列出Yin等人(1999)的n_1=2的算法加以比较.

符号差类运输问题的多项式时间算法

给出符号差类运输问题的一个多项式时间算法， 并证明该算法的时间复杂性是 Ｏ（ｍ ｎ２ ＋ ｍ ２ ｎ）．

一个求外平面图最小反馈点集的多项式时间算法

如果从一个图中去掉某些顶点后得到的导出子图是无圈图 ,则所去的那些顶点组成的集合就是原图的反馈点集。本文讨论外平面图的反馈点集并给出了一个求外平面图最小反馈点集的多项式时间算法。

单位加工时间入树约束Open Shop问题的多项式时间算法

本文研究具有单位加工时间及入树约束的ＯｐｅｎＳｈｏｐ问题，提出了一个多项式时间算法，该算法根据入树约束的层次结构分批安排加工，使每批加工解除约束的工件数最多。文章证明，算法的计算量为Ｏ（ｎ＾２）。

一类耦合工件组作业问题的多项式时间算法

耦合工件是指一个需经两次不同操作的工件,且这两次操作具有先后次序和一定的时间间隔.给定一组耦合工件,要求确定这些工件在一台机器上的加工顺序及时间安排,使加工全长达到最小,这就是耦合工件组作业问题.对一般情形,该问题已被证明为NP困难.本文讨论并给出了由n个相同的耦合工件构成的耦合工件组作业问题的多项式时间算法.

一个SNP问题的多项式时间算法

讨论关于单体型的无间隙的最小单核苷酸多态性位点的移去问题.通过分析其对应图模型的性质讨论问题等价形式;证明求解该问题等价于求对应图的最大独立集与独立数;给出求最大独立集与独立数的算法,从而得到此问题的有效的多项式时间算法.

瓶颈指派问题的一种多项式时间算法

本文对瓶颈指派问题给出了一种新的算法，该算法不需要利用最大流算法，而类似于解经典指派问题的匈牙利算法。该算法是一个多项式时间算法，其复杂性为Ｏ（ｎ３）

基于局部self-concordant障碍函数的全牛顿步多项式时间算法(英文)

由Nesterov和Nemirovski^([4])创立的self-concordant障碍函数理论为解线性和凸优化问题提供了多项式时间内点算法.根据self-concordant障碍函数的参数,就可以分析内点算法的复杂性.在这篇文章中,我们介绍了基于核函数的局部self-concordant障碍函数,它在线性优化问题的中心路径及其邻域内满足self-concordant性质.通过求解此障碍函数的局部参数值,我们得到了求解线性规划问题的基于此局部Self-concordant障碍函数的纯牛顿步内点算法的理论迭代界.此迭代界与目前已知的最好的理论迭代界是一致的.

哈密顿图判定问题的多项式时间算法

NP=?P(即NP是否等于P)的问题是计算机科学和数学中的重要问题。美国克雷数学研究院将其列为新千年七大困难问题之首,2005年Science将其列为25个困难问题之19。Science最近列出的125个亟待解决的重要问题中,第19个问题实质上就是NP=?P的问题。如果NP=P,对于很多困扰科学研究的困难计算问题,理论上就存在多项式时间算法来迅速求解它们。而现代密码学建立在NP≠P的假设之上。人们希望存在难解问题,希望基于难解问题构造加密算法,希望能够利用难解问题的求解复杂性对抗分析和攻击。如果NP=P,所有在NP≠P假定之上开展的计算研究都至少需要重新审视其意义。NP完全问题的求解复杂性决定NP=P是否成立。针对一个被称为MSP问题的新问题,文中提出了一个关于MSP问题的多项式时间算法,并给出了该算法的证明和时间复杂性分析。由于已经发表了十多个经典的NP完全问题到MSP问题的归结以及MSP问题到SAT问题的归结,因此MSP问题存在多项式时间算法这样一个研究结果对于研究NP=P有重要和积极的意义。

单机分批加工最大迟后问题的一个多项式时间算法

文中考虑下述单机分批问题：对时刻零同时到达的ｎ个工件需分成若干批在同台机器上加工，同批工件加工时相邻，任一工件的完工时间为所在批中全部工件完工时的时间，机器每加工一批工件需一相同的调整时间．文中以工件的最大迟后为目标函数，对工件加工顺序预先给定和可任意时的最优分批分别给出了多项式时间算法．

多机排序问题pm｜fix_j，pmtn｜C_（max）的多项式时间算法

在经典排序论中，一般都作以下两条假设：其一是每台机器在任一时刻至多加工一个零件，其二是每个零件在任一时刻至多被一台机器加工．在这篇文章中，研究多台机器可同时加工一个零件的多机排序问题，且每个零件可在固定的一个机器的子集上加工．本文在机器总数确定，零件加工可间断的条件下，设计出求这类问题最优解的计算方法，并研究了这种问题的计算复杂性．

几何规划的一种多项式时间算法

利用几何规划的特点，借助于对偶理论，把原始对偶道路跟踪内点算法，推广应用于正定式几何规划，并证明了此算法对于无约束正定式几何规划是一种多项式时间算法，可以预料，这种算法可推广应用于约束几何规划问题。

3度图的最小顶点覆盖问题的多项式时间算法

最小顶点覆盖问题是图论和组合数学中经典的NP-Hard问题之一,在实际问题中有着广泛的应用.本文首先给出最小顶点覆盖问题的若干性质,然后根据这些性质设计了3度图最小顶点覆盖问题的一个多项式时间算法,并通过2个实例对算法进行了说明.