两台同类机排序问题SPT算法的最坏情况比

本文研究以工件总完工时间为目标函数的两台同类机排序问题, 给出了SPT算法以两台机器速度比为参数的最坏情况比, 使该算法的常数最坏情况比上界与下界的差距由0.430 5减小到0.014 7。     

带有运输且加工具有灵活性的无等待流水作业排序问题

研究一类带有运输且加工具有灵活性的两阶段无等待流水作业排序问题, 其中每阶段只有一台机器, 每个工件有两道工序需要依次在两台机器上加工, 工件在两台机器上的加工及两道工序之间不允许等待. 给出两种近似算法, 并分别分析其最坏情况界. 第一种算法是排列排序, 证明了最坏情况界不超过5/2; 第二种算法将工件按照两道工序加工时间之和的递增顺序排序, 证明其最坏情况界不超过2. 最后, 通过数值模拟比较算法的性能. 对问题中各参数取不同值的情况, 分别生成若干个实例, 用算法得到的解与最优解的下界作比值, 通过分析这些比值的最大值、最小值和平均值来比较上述两个算法的性能.     

可转包两台流水作业机排序的近似算法

研究可转包的两台流水作业机排序问题, 目标是极小化最大完工时间和总外包费用之和. 首先给出最坏情况界为2的近似算法, 接着对工件满足有序化约束的情形给出最坏情况界为\frac{3}{2}的改进算法, 以上算法界均为紧界.     

带机器准备时间的平行机在线与半在线排序

本文研究带机器准备时间的m台平行机系统在线和半在线排序问题.对在线排序问题,我们证明了LS算法的最坏情况界为2-1/m.对已知工件加工时间递减,已知总加工时间和已知工件最大加工时间三个半在线模型,我们分析了它们的下界和所给算法的最坏情况界.对其中两台机情形均得到了最好近似算怯。     

带机器准备时间的机器覆盖问题的在线、半在线算法

研究以极大化最小机器负载为目标的机器带准备时间的同型机排序问题.证明了LS算法是求解该问题的最好的在线算法,它的最坏情况界为1/m.同时给出了求解两台机的预先知道工件最大加工时间,预先知道工件集的总加工时间以及预先知道工件从大到小到达这三种情形下最好的半在线算法,这三个算法的最坏情况界分别为2/3,2/3以及3/4.     

具有优先权和准备时间的自由作业时间表问题

研究具有优先权和准备时间的自由作业时间表问题 ,在稠密时间表的情况下 ,给出一种启发式算法 ,猜想该算法的紧界是 2 -2 /( m +1 ) ,其中 m是机器台数 .对于只有两台机器的情况 ,即当 m =2 时 ,证明该算法的最坏性能比是 4/3 ,并通过实例证明上界是紧的 .     

极大化提前完工总量平行机排序问题的LPT算法

研究带有共同交货期的三台平行机排序问题。工件在加工过程中不允许中断, 目标是极大化所有工件的提前完工量, 即在交货期前所加工工件(或部分) 的总加工时长。由于该问题是NP-难问题, 本文应用经典LPT算法来解决该问题。我们证明了LPT算法求解该问题的最坏情况界至多为$\frac{15}{13}$, 并给出实例说明最坏情况界的下界为$\frac{27}{25}$。     

P‖Cmin随机算法研究

本文研究了P‖Cmin的随机算法及其最坏情况界，我们给出了Pm‖Cmin在线排序问题新的随机上界，并给出了P2‖Cmin的最好随机算法，其最坏情况界为2／3。对P2‖Cmin已知工件加工时间递减半在线模型，我们给出了一最坏情况界为6／7的随机算法并证明了它为最好的。     

带约束的平行机排序的一个近似算法

讨论有资源约束和有机器准备时间的平行机排序问题,资源约束为每个机器至多可加工k个工件,在极小化makespan的上给出了一个匹配算法,证明其最坏情况最紧界是2-m^-1,并进一步给出了它的两个带参数的最坏情况界。     

极大化提前完工总量平行机排序问题的LPT算法

研究带有共同交货期的三台平行机排序问题。工件在加工过程中不允许中断, 目标是极大化所有工件的提前完工量, 即在交货期前所加工工件(或部分) 的总加工时长。由于该问题是NP-难问题, 本文应用经典LPT算法来解决该问题。我们证明了LPT算法求解该问题的最坏情况界至多为$\frac{15}{13}$, 并给出实例说明最坏情况界的下界为$\frac{27}{25}$。     

A new bound for the quadratic assignment problem based on convex quadratic programming

We describe a new convex quadratic programming bound for the quadratic assignment problem (QAP). The construction of the bound uses a semidefinite programming representation of a basic eigenvalue bound for QAP. The new bound dominates the well-known projected eigenvalue bound, and appears to be competitive with existing bounds in the trade-off between bound quality and computational effort. Received: February 2000 / Accepted: November 2000?Published online January 17, 2001     

Error bounds for spatial discretization and waveform relaxation applied to parabolic functional differential equations

The process of semi-discretization and waveform relaxation are applied to general nonlinear parabolic functional differential equations. Two new theorems are presented, which extend and improve some of the classical results. The first of these theorems gives an upper bound for the norm of the error of finite difference semi-discretization. This upper bound is sharper than the classical error bound. The second of these theorems gives an upper bound for the norm of the error, which is caused by both semi-discretization and waveform relaxation. The focus in the paper is on estimating this error directly without using the upper bound for the error, which is caused by the process of semi-discretization and the upper bound for the error, which is caused by the waveform relaxation method. Such estimating gives sharper error bound than the bound, which is obtained by estimating both errors separately.     

Global error bound for convex inclusion problems

The existence of global error bound for convex inclusion problems is discussed in this paper, including pointwise global error bound and uniform global error bound. The existence of uniform global error bound has been carefully studied in Burke and Tseng (SIAM J. Optim. 6(2), 265–282, 1996) which unifies and extends many existing results. Our results on the uniform global error bound (see Theorem 3.2) generalize Theorem 9 in Burke and Tseng (1996) by weakening the constraint qualification and by widening the varying range of the parameter. As an application, the existence of global error bound for convex multifunctions is also discussed.     

A graph for which the inertia bound is not tight

The inertia bound gives an upper bound on the independence number of a graph by considering the inertia of matrices corresponding to the graph. The bound is known to be tight for graphs on 10 or fewer vertices as well as for all perfect graphs. It is natural to question whether the bound is always tight. We show that the bound is not tight for the Paley graph on 17 vertices as well as its induced subgraph on 16 vertices.     

On the Geil–Matsumoto bound and the length of AG codes

The Geil–Matsumoto bound conditions the number of rational places of a function field in terms of the Weierstrass semigroup of any of the places. Lewittes’ bound preceded the Geil–Matsumoto bound and it only considers the smallest generator of the numerical semigroup. It can be derived from the Geil–Matsumoto bound and so it is weaker. However, for general semigroups the Geil–Matsumoto bound does not have a closed formula and it may be hard to compute, while Lewittes’ bound is very simple. We give a closed formula for the Geil–Matsumoto bound for the case when the Weierstrass semigroup has two generators. We first find a solution to the membership problem for semigroups generated by two integers and then apply it to find the above formula. We also study the semigroups for which Lewittes’s bound and the Geil–Matsumoto bound coincide. We finally investigate on some simplifications for the computation of the Geil–Matsumoto bound.     

A Cramér–Rao inequality for non-differentiable models

We compute a variance lower bound for unbiased estimators in statistical models. The construction of the bound is related to the original Cramér–Rao bound, although it does not require the differentiability of the model. Moreover, we show our efficiency bound to be always greater than the Cramér–Rao bound in smooth models, thus providing a sharper result.     

A New Semidefinite Programming Bound for Indefinite Quadratic Forms Over a Simplex

The paper describes a method for computing a lower bound of the global minimum of an indefinite quadratic form over a simplex. The bound is derived by computing an underestimator of the convex envelope by solving a semidefinite program (SDP). This results in a convex quadratic program (QP). It is shown that the optimal value of the QP is a lower bound of the optimal value of the original problem. Since there exist fast (polynomial time) algorithms for solving SDP's and QP's the bound can be computed in reasonable time. Numerical experiments indicate that the relative error of the bound is about 10 percent for problems up to 20 variables, which is much better than a known SDP bound.     

An interval branch and bound algorithm for bound constrained optimization problems

In this paper, we propose modifications to a prototypical branch and bound algorithm for nonlinear optimization so that the algorithm efficiently handles constrained problems with constant bound constraints. The modifications involve treating subregions of the boundary identically to interior regions during the branch and bound process, but using reduced gradients for the interval Newton method. The modifications also involve preconditioners for the interval Gauss-Seidel method which are optimal in the sense that their application selectively gives a coordinate bound of minimum width, a coordinate bound whose left endpoint is as large as possible, or a coordinate bound whose right endpoint is as small as possible. We give experimental results on a selection of problems with different properties.     

Improving Christofides' lower bound for the traveling salesman problem

In 1972 Christofides introduced a lower bound for the Traveling Salesman Problem (TSP). The bound is based on solving repeatedly a Linear Assignment Problem. We relate the bound to the Complete Cycle Problem; as a consequence the correctness of the bound is easier to prove.

Further we give improvements for the bound in the symmetric case and we deal with the influence of the triangle equation together with the identification of non-optimal edges for the TSP. The improvements are illustrated by examples and computational results for large problems.     

A strengthened Barvinok-Pataki bound on SDP rank

The Barvinok-Pataki bound provides an upper bound on the rank of extreme points of a spectrahedron. This bound depends solely on the number of affine constraints of the problem, i.e., on the algebra of the problem. Specifically, the triangular number of the rank r is upper bounded by the number of affine constraints. We revisit this bound and provide a strengthened upper bound on the rank using the singularity degree of the spectrahedron. Thus we bring in the geometry and stability of the spectrahedron, i.e., increased instability as seen by higher singularity degree, yields a lower, strengthened rank bound.