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.     

A Feigenbaum sequence of bifurcations in the Lorenz model

For some high values of the Rayleigh numberr, the Lorenz model exhibits laminar behavior due to the presence of a stable periodic orbit. A detailed numerical study shows that, forr decreasing, the turbulent behavior is reached via an infinite sequence of bifurcations, whereas forr increasing, this is due to a collapse of the stable orbit to a hyperbolic one. The infinite sequence of bifurcations is found to be compatible with Feigenbaum's conjecture.     

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.     

Conditions for the convergence in distribution of maxima of stationary normal processes

The asymptotic distribution of the maximum M_n=max_1?t?nξ_t in a stationary normal sequence ξ₁,ξ,… depends on the correlation r_t between ξ₀ and ξ_t. It is well known that if r_t log t → 0 as t → ∞ or if Σr²_t<∞, then the limiting distribution is the same as for a sequence of independent normal variables. Here it is shown that this also follows from a weaker condition, which only puts a restriction on the number of t-values for which rt log t islarge. The condition gives some insight into what is essential for this asymptotic behaviour of maxima. Similar results are obtained for a stationary normal process in continuous time.     

Central limit theorem and weak law of large numbers with rates for martingales in Banach spaces

This paper is concerned with large-$\text{O}$ error estimates concerning convergence in distribution as well as norm convergence for Banach space-valued martingale difference sequences. Indeed, two general limit theorems equipped with rates of convergence for such difference sequences are established. Applications of these lead to the central limit theorem and the weak law of large numbers with rates for Banach space-valued martingales.     

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.     

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.     

Measurements of motionally averaged heteronuclear dipolar couplings in MAS NMR using R-type recoupling

A novel MAS NMR approach is presented for the determination of heteronuclear dipolar couplings in unoriented materials. The technique is based on the proton-detected local field (PDLF) protocol, and achieves dipolar recoupling by R-type radio-frequency irradiation. The experiment, which is called R-PDLF spectroscopy, is demonstrated on solid and liquid-crystalline systems. For mobile systems, it is shown that the R-PDLF scheme provides better dipolar resolution as compared to techniques combining conventional separated local field (SLF) spectroscopy with R-type recoupling.     

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.