1) polynomial time algorithm
多项式时间算法
1.
A polynomial time algorithm for the scheduling problem of identical coupled-task jobs is presented in.
本文讨论并给出了由n个相同的耦合工件构成的耦合工件组作业问题的多项式时间算法。
2.
To present a new polynomial time algorithm for China traveling salesman problem, first, point set was partitioned into a number of subpoint sets by using convex hull and medial axis.
研究求解中国货郎担问题最短回路的多项式时间算法。
3.
In this paper,we will prove that there exit an orthogonal matching decomposition of M in simple bipartite graph,and present a polynomial time algorithm of this decomposition.
在本文中我们将证明对于简单二部图G,存在关于完美匹配M的正交匹配分解,并给出了求这个分解的多项式时间算法。
2) polynomial-time algorithm
多项式时间算法
1.
In this paper,we gave two polynomial-time algorithms for solving two special unit type shortest path improvement problems under Hamming distance in single-source arborescence,and we studied some properties of the general problem.
给出了求解两类特殊的Hamming距离下单位型单发点树型网络最短路改进问题的多项式时间算法,并研究了一般树型网络下该问题的性质。
2.
Finally a polynomial-time algorithm for the optimal strategy of OEM is gotten by using dual theory of bilevel programming.
最后,利用双层规划的对偶理论,给出求解OEM业务最优策略的一种多项式时间算法。
3.
It is shown that this algorithm is a polynomial-time algorithm which can algorithm can find anε-approximate solution in O(n~(1/2)lnε~(-1)) iterations.
给出二次锥规划的一种不可行内点算法并证明该算法是多项式时间算法。
4) fully polynomial time approximation scheme
全多项式时间近似算法
1.
We discuss maximum multicommodity flow problem with budget constraint,present fully polynomial time approximation scheme for this problem that is independent of the number of commodities k,the complexity of the algorithm is (ε~(-2)m~2).
研究有预算限制的最大多种物资流问题,给出了这个问题的不依赖物资数k的全多项式时间近似算法,其算法复杂性是O~(-ε2m2)。
5) pseudo-polynomial algorithm
拟多项式时间算法
1.
Study the pseudo-polynomial algorithm for the k-(n_1,1,.
研究Wikum提到的关于带有延迟时间下界的k (n1,1,…,1) 链形结构排序问题的拟多项式时间算法,其中n1=2的情况己得到解决,这里主要以n1=3的情形为例作更加细致的分析,然后给出此原来的算法更加有效的拟多项式时间算法。
6) pseudopolynomial algorithm
伪多项式时间算法
1.
For the problem of minimizing F 1 and F 2 simultaneously, this paper develops a pseudopolynomial algorithm for the construction of the efficient point set.
对 F1 、F2 的同时极小化 ,文中给出可构造有效点集的伪多项式时间算法 。
补充资料：多项式时间归约
多项式时间归约
polynomial time reduction
L’(扛，则L就是节中(在多项式时间图灵归约下)“最困难”的，称其为够T-完全的。多项式时间图灵归约又称为库克归约。由多项式时间图灵归约的定义，很自然地可产生另一种重要的多项式时间归约，即多项式时间非确定图灵归约。多项式时间图灵归约与多项式时间非确定图灵归约的区别仅在于前者使用的是多项式时间确定型。拍cle机器，后者使用的是多项式时间非确定型优acle机器。 R.心印于1972年利用多项式时间多一归约来刻画NP类中的“最困难”问题类。同时，R.Karp给出了21个属于这类问题的实例，它们涉及到逻辑、图论及组合优化等学科中的经典计算问题。对于乏上的两个语言Ll，LZ，若存在多项式时间可计算函数f:乞份~乏甘，使得对任何xe艺诀，x任Ll当且仅当f(x)eL:，则称L;多项式时间多一归约到L:，记为Ll簇二LZ。这时，x任L，的判别可以通过计算f(x)，转化成f(x)‘LZ的判别。因此，L，(二LZ更直观地理解为Ll的计算不比LZ的计算困难。同群类似讨论，簇二也可定义在任何语言类留上，若存在Le留，使对于任何L‘任昭，都有L‘戳L，则称L为哈m-完全的。多项式时间多一归约又称为卡普归约。 递归论中的其它归约都可通过多项式变形成为一种多项式时间归约。上述介绍的几种归约关系已成为计算复杂性理论的重要工具。duox}angshi shlJ!Qn guiyue多项式时间归约(polynomial tilne阁uc·tion)一种常用的、归约函数是多项式时间可计算的复杂性归约。5.Gl)k于1971年利用多项式时间图灵归约，定义了NP类中的“最困难”问题。并证明了判别布尔表达式的可满足性问题(SA’T)，是这类问题的第一个问题。 假设所考虑的问题都已编码成字母表乏上的语言(实例的集合)。设L;，L:是乏上两个语言，若存在以L:为orade集的多项式时间图灵机M，其接受的语言为Ll，则称L，多项式时间图灵归约到LZ，记为Ll簇扛2。这时，对x是否属于L，的判别可转化为至多{x{的多项式个元素是否属于L:的判别，因此，LZ任P便导致Ll任P。从这种相对的意义上讲，Ll的计算不比I.z困难。 落孚可以是定义在任何语言类节上的一种二元前序关系，如果存在L任节，对于任何L’任留，都有
说明：补充资料仅用于学习参考，请勿用于其它任何用途。
参考词条