On random algebraic polynomials

This paper provides asymptotic estimates for the expected number of real zeros and -level crossings of a random algebraic polynomial of the form , where are independent standard normal random variables and is a constant independent of . It is shown that these asymptotic estimates are much greater than those for algebraic polynomials of the form .

     

关于Duphantus方程(a~lx~m+c)/(abx+d)=by~2的一类解

通过对Ｄｕｐｈａｎｔｕｓ方程的研究，得到了当及时各种情况的全部正整数解。     

A dynamic production planning and scheduling algorithm for two products processed on one line

This paper presents a dynamic production planning and scheduling algorithm for two products processed on one line over a fixed time horizon. Production rates are assumed fixed, and restrictions are placed or inventory levels and production run lengths. The resulting problem is a nonlinear binary program, which is solved using an implicit enumeration strategy. The algorithm focuses on the run changeover period while developing tighter bounds on the length of the upcoming run to improve computational efficiency. About 99% pf 297 randomly generated problems with varying demand patterns are solved in less than 15 seconds of CPU time on a CDC Cyber 172 Computer. A mixed integer programming formulation of the generalized multi-product case under no-backlogging of demand is also given.     

Operations that preserve total dual integrality

There are many useful operations, such as adding slack variables, taking scalar multiples of inequalities, and applying Fourier-Motzkin elimination, that can be performed on a linear system such that if the system defines an integer polyhedron then so does the derived system. The topic dealt with here is whether or not these operations also preserve total dual integrality of linear systems.     

Capital budgeting with benders decomposition

Capital budgeting problems with different interest rates for borrowing and lending and with possible limits on borrowing are applied to dual and primal decomposition. While the former fails if a dual gap exists, the latter becomes attractive. The paper elaborates dual and primal decomposition to capital budgeting models and discusses variants of the Benders scheme. A computer implementation is described and results of extensive computer runs with different strategies are reported which give proof of the efficiency of the implemented decomposition procedure.     

Integer programming formulations of vehicle routing problems

Various mathematical formulations are available for situations represented by vehicle routing problems. The assignment-based integer programming formulations of these problems are more common and easy to understand. Such formulations are discussed in this paper and a much simpler formulation for the vechicle routing problem is presented for the case, when all the vehicles have the same load capacity and maximum allowable cost per route.     

Unitarily Inequivalent Representations in Algebraic Quantum Theory

It has been maintained that the physical content of a model of a system is completely contained in the C∗-algebra of quasi-local observables that is associated with the system. The reason given for this is that the unitarily inequivalent representations of are physically equivalent. But, this view is dubious for at least two reasons. First, it is not clear why the physical content does not extend to the elements of the von Neumann algebras that are generated by representations of . It is shown here that although the unitarily inequivalent representations of are physically equivalent, the extended representations are not. Second, this view detracts from special global features of physical systems such as temperature and chemical potential by effectively relegating them to the status of fixed parameters. It is desirable to characterize such observables theoretically as elements of the algebra that is associated with a system rather than as parameters, and thereby give a uniform treatment to all observables. This can be accomplished by going to larger algebras. One such algebra is the universal enveloping von Neumann algebra, which is generated by the universal representation of ; another is the direct integral of factor representations that are associated with the set of values of the global features. Placing interpretive significance on the von Neumann algebras mentioned earlier sheds light on the significance of unitarily inequivalent representations of , and it serves to show the limitations of the notion of physical equivalence.     

Approximating disjoint-path problems using packing integer programs

In a packing integer program, we are given a matrix $A$ and column vectors $b,c$ with nonnegative entries. We seek a vector $x$ of nonnegative integers, which maximizes $c^{T}x,$ subject to $Ax \leq b.$ The edge and vertex-disjoint path problems together with their unsplittable flow generalization are NP-hard problems with a multitude of applications in areas such as routing, scheduling and bin packing. These two categories of problems are known to be conceptually related, but this connection has largely been ignored in terms of approximation algorithms. We explore the topic of approximating disjoint-path problems using polynomial-size packing integer programs. Motivated by the disjoint paths applications, we introduce the study of a class of packing integer programs, called column-restricted. We develop improved approximation algorithms for column-restricted programs, a result that we believe is of independent interest. Additional approximation algorithms for disjoint-paths are presented that are simple to implement and achieve good performance when the input has a special structure.Work partially supported by NSERC OG 227809-00 and a CFI New Opportunities Award. Part of this work was done while at the Department of Computer Science, Dartmouth College and partially by NSF Award CCR-9308701 and NSF Career Award CCR-9624828.This work was done while at the Department of Computer Science, Dartmouth College and partially supported by NSF Award CCR-9308701 and NSF Career Award CCR-9624828.     

On Tori Triangulations Associated with Two-Dimensional Continued Fractions of Cubic Irrationalities

The notion of equivalence of multidimensional continued fractions is introduced. We consider some properties and state some conjectures related to the structure of the family of equivalence classes of two-dimensional periodic continued fractions. Our approach to the study of the family of equivalence classes of two-dimensional periodic continued fractions leads to revealing special subfamilies of continued fractions for which the triangulations of the torus (i.e., the combinatorics of their fundamental domains) are subjected to clear rules. Some of these subfamilies are studied in detail; the way to construct other similar subfamilies is indicated.     

An Implementation for the Algorithm of Janet bases of Linear Differential Ideals in the Maple System

In this paper, an algorithm for computing the Janet bases of linear differential equations is described, which is the differential analogue of the algorithm JanetBasis improved by Gerdt. An implementation of the algorithm in Maple is given. The implemented algorithm includes some subalgorithms: Janet division,Pommaret division, the judgement of involutive divisor and reducible, the judgement of conventional divisor and reducible, involutive normal form and conventional normal form, involutive autoreduction and conventional autoreduction, PJ-autoreduction and so on. As an application, the Janet Bases of the determining system of classical Lie symmetries of some partial differential equations are obtained using our package.