主指标为最大延迟的主次指标分批排序问题

研究现代排序问题—主指标为最大延迟的主次指标分批排序问题.这里利用动态规划的递推法给出了次指标分别为最大完工时间和误工总数时的多项式时间算法,并给出了次指标为关于工件完工时间的任意正规函数时的拟多项式时间算法.     

带机器准备时间的平行机排序问题

研究了带机器准备时间的m台平行机排序问题,设计出了一个多项式时间近似方案(PTAS),并给出了一个机器数m为固定常数的情形下的全多项式时间近似方案(FPTAS).     

多项式时间度的极小对分裂

本文讨论多项式时间度的极小对分裂问题．证明了尽管有些非零多项式时间度不能分裂成极小对，但是任何非零的多项式时间度都可分裂成两个或两个以上的极小对之并的形式，也可分裂成一个多项式时间度与一组两两互成极小对的多项式时间度之并的形式．本文构造了Ｃ￣ｎ中单位球Ｂ￣ｎ和多圆盘△￣ｎ的（０，１）型热核形式，作为应用，我们给出了多圆盘上方程解的积分表示．     

一个求线性代数方程组非负解的算法及其在线性规划中的应用

1.引言关于线性规划的多项式算法,哈奇扬于1979年首先把一个线性规划问题化成一个线性不等式组的求解问题,然后用椭球方法求解线性不等式组,并证明是多项式时间可解的。Karmarkar于1984年也给出了一个求解线性规划的多项式时间解法,他     

基于加工时间之和学习效应下的单机成组排序问题

研究具有加工时间之和学习效应下的一个新型成组排序问题,工件的学习效应是之前工件加工时间之和的函数,组学习效应是成组加工所在的位置的函数. 考虑最大完工时间和总完工时间两个问题,证明了这两个问题都是多项式时间可解的,并提出了相应的多项式时间算法.     

系列平行图上带时间约束的Steiner最小树问题

对一类特殊系列平行图上带有时间约束的Steiner最小树问题,证明了其复杂性为NPC,并给出了一个完全多项式时间近似方案.     

航空器供油问题中完全逆序类中的多项式时间可解类

航空器供油问题是一类非线性组合优化问题,其目标函数为分式形式,该问题目前不存在多项式时间算法,也未被证明是NP完全问题。一般可以用置换来刻画n架飞机的一个供油顺序。该问题中有一类实例被称为“完全逆序类”,“完全逆序类”用动态规划算法求解计算时间为O(n2ⁿ),具有指数时间复杂度。本文通过对该“完全逆序类”问题做进一步分析,发现在“完全逆序类”中也存在着多项式时间可解的情况。定理1研究一类一次可解的情况,若问题满足定理1的条件,则求解一次即可找到其最优解;定理2研究一类多项式时间可解的情况,当问题满足定理2的条件时,其最优解可在多项式时间内获得。     

需要安装时间的两台多功能机排序问题的计算复杂性

提出需要安装时间的多功能机排序问题,一般情况下,这是NP-困难的;主要研究只有两台机器时一些特殊情况下的计算复杂性.根据加工集合为机器全集的工件组数的不同,分别给出多项式时间算法和分枝定界算法.对各工件组的工件数和加工时间都相等的情况,给出一个多项式时间的最优算法-奇偶算法,从而证明此问题是多项式时间可解的.     

一个约束乘积最大问题的强多项式时间算法

本文讨论了约束乘积最大问题最优解的结构特征,在此基础上给出了一个计算时间为O(n2)的强多项式时间算法,并且对于单边约束的情形给出了复杂度更低(O(nlnn))的强多项式时间算法.     

具有老化效应的单机共同工期安排和工件可拒绝排序问题

研究共同工期安排和具有老化效应的单机排序问题。在整个加工过程中,工件的实际加工时间是与其所在位置和工件本身老化率相关的函数,生产商可以通过支付一定的处罚费用而拒绝加工某些工件。鉴于生产过程中出现老化效应,通过采取维修活动来提高生产率。目标是划分接受工件集和拒绝工件集,确定接受工件集中工件的加工次序和维修活动安排的位置,以极小化接受工件的提前、延误、工期与拒绝工件的总处罚费用的加权和。对这一问题,首先将其转化为指派问题并构造了最优多项式时间算法;其次,证明了目标函数满足一定条件下的问题的更一般形式能够在多项式时间内得到最优解;最后,对本文问题的一个特殊情况,设计了具有更低时间复杂度的多项式动态规划算法。     

Polynomial Algorithms for a Class of Discrete Minmax Linear Programming Problems

We consider the problem of obtaining integer solutions to a minmax linear programming problem. Although this general problem is NP-complete, it is shown that a restricted version of this problem can be solved in polynomial time. For this restricted class of problems two polynomial time algorithms are suggested, one of which is strongly polynomial whenever its continuous analogue and an associated linear programming problem can be solved by a strongly polynomial algorithm. Our algorithms can also be used to obtain integer solutions for the minmax transportation problem with an inequality budget constraint. The equality constrained version of this problem is shown to be NP-complete. We also provide some new insights into the solution procedures for the continuous minmax linear programming problem.     

The complexity of approximating a nonlinear program

We consider the problem of finding the maximum of a multivariate polynomial inside a convex polytope. We show that there is no polynomial time approximation algorithm for this problem, even one with a very poor guarantee, unless P = NP. We show that even when the polynomial is quadratic (i.e. quadratic programming) there is no polynomial time approximation unless NP is contained in quasi-polynomial time.Our results rely on recent advances in the theory of interactive proof systems. They exemplify an interesting interplay of discrete and continuous mathematics—using a combinatorial argument to get a hardness result for a continuous optimization problem.     

工件加工时间增加的排序问题(1‖Cmax)

讨论了工件加工时间随工件开工时间线性增加的排序问题,考虑的目标函数是最大完工时间,证明了加工时间是简单线性增加情况下最大完工时间问题是多项式时间可解的,对于加工时间是一般线性增加情况,研究了最优排序的性质,同时证明了两种特殊情况下最大完工时间问题也是多项式时间可解的。     

Polynomial-time algorithms for regular set-covering and threshold synthesis

A set-covering problem is called regular if a cover always remains a cover when any column in it is replaced by an earlier column. From the input of the problem - the coefficient matrix of the set-covering inequalities - it is possible to check in polynomial time whether the problem is regular or can be made regular by permuting the columns. If it is, then all the minimal covers are generated in polynomial time, and one of them is an optimal solution. The algorithm also yields an explicit bound for the number of minimal covers. These results can be used to check in polynomial time whether a given set-covering problem is equivalent to some knapsack problem without additional variables, or equivalently to recognize positive threshold functions in polynomial time. However, the problem of recognizing when an arbitrary Boolean function is threshold is NP-complete. It is also shown that the list of maximal non-covers is essentially the most compact input possible, even if it is known in advance that the problem is regular.     

Weighted matching with pair restrictions

The weighted matroid parity problems for the matching matroid and gammoids are among the very few cases for which the weighted matroid parity problem is polynomial time solvable. In this work we extend these problems to a general revenue function for each pair, and show that the resulting problem is still solvable in polynomial time via a standard weighted matching algorithm. We show that in many other directions, extending our results further is impossible (unless P = NP). One consequence of the new polynomial time algorithm is that it demonstrates, for the first time, that a prize-collecting assignment problem with “pair restriction” is solved in polynomial time. The prize collecting assignment problem is a relaxation of the prize-collecting traveling salesman problem which requires, for any prescribed pair of nodes, either both nodes of the pair are matched or none of them are. It is shown that the prize collecting assignment problem is equivalent to the prize collecting cycle cover problem which is hence solvable in polynomial time as well.     

A strongly polynomial FPTAS for the symmetric quadratic knapsack problem

The symmetric quadratic knapsack problem (SQKP), which has several applications in machine scheduling, is NP-hard. An approximation scheme for this problem is known to achieve an approximation ratio of (1 + ?) for any ? > 0. To ensure a polynomial time complexity, this approximation scheme needs an input of a lower bound and an upper bound on the optimal objective value, and requires the ratio of the bounds to be bounded by a polynomial in the size of the problem instance. However, such bounds are not mentioned in any previous literature. In this paper, we present the first such bounds and develop a polynomial time algorithm to compute them. The bounds are applied, so that we have obtained for problem (SQKP) a fully polynomial time approximation scheme (FPTAS) that is also strongly polynomial time, in the sense that the running time is bounded by a polynomial only in the number of integers in the problem instance.     

On the computational complexity of a merge recognition problem

A problem arising from the work of C.A.R. Hoare on parallel programming is that of deciding whether a given string ? is a “merge” of two other given strings σ and τ. We describe a polynomial time algorithm for this problem. This algorithm can easily be extended to check, in polynomial time, whether ? is a merge of any fixed number of strings. The problem for an arbitrary number of strings is shown to be NP-complete and so is unlikely to have a polynomial time algorithm.     

N-fold integer programming and nonlinear multi-transshipment

The multi-transshipment problem is NP-hard already for two commodities over bipartite networks. Nonetheless, using our recent theory of n-fold integer programming and extensions developed herein, we are able to establish the polynomial time solvability of the problem in two broad situations. First, for any fixed number of commodities and number of suppliers, we solve the problem over bipartite networks with variable number of consumers in polynomial time. This is very natural in operations research applications where few facilities serve many customers. Second, for every fixed network, we solve the problem with variable number of commodities in polynomial time.     

An inverse model for the most uniform problem

In this paper, we consider a kind of inverse model for the most uniform problem. This model has some practical background. It is shown that the model can be solved in polynomial time whenever an associated min-sum problem can be solved in polynomial time.     

The complexity of the equivalence and equation solvability problems over nilpotent rings and groups

It is proved that the equation solvability problem can be solved in polynomial time for finite nilpotent rings. Ramsey’s theorem is employed in the proof. Then, using the same technique, a theorem of Goldmann and Russell is reproved: the equation solvability problem can be solved in polynomial time for finite nilpotent groups.