A single supplier–single retailer system with an order-up-to level inventory policy

We consider a two-level vendor-managed system in which external demand occurs only at a retailer and a supplier replenishes the retailer employing an order-up-to S policy over T periods. We present an O(T³) algorithm to coordinate the system when S is known. We also show that S can be optimized in O(aT³) time for an input parameter a.     

An Efficient Procedure for Dynamic Lot-sizing Model with Demand Time Windows

We consider a dynamic lot-sizing model with demand time windows where n demands need to be scheduled in T production periods. For the case of backlogging allowed, an O(T ³) algorithm exists under the non-speculative cost structure. For the same model with somewhat general cost structure, we propose an efficient algorithm with O(max {T ², nT}) time complexity.     

Speeding up the Dreyfus–Wagner algorithm for minimum Steiner trees

The Dreyfus–Wagner algorithm is a well-known dynamic programming method for computing minimum Steiner trees in general weighted graphs in time O ^*(3 ^k ), where k is the number of terminal nodes to be connected. We improve its running time to O ^*(2.684 ^k ) by showing that the optimum Steiner tree T can be partitioned into T = T ₁∪ T ₂ ∪ T ₃ in a certain way such that each T _i is a minimum Steiner tree in a suitable contracted graph G _i with less than terminals. In the rectilinear case, there exists a variant of the dynamic programming method that runs in O ^*(2.386 ^k ). In this case, our splitting technique yields an improvement to O ^*(2.335 ^k ).     

Fast solution of toeplitz systems of equations and computation of Padé approximants

We present two new algorithms, ADT and MDT, for solving order-n Toeplitz systems of linear equations Tz = b in time O(n log²n) and space O(n). The fastest algorithms previously known, such as Trench's algorithm, require time $\text{Ω(n}{}^2\text{)}$ and require that all principal submatrices of T be nonsingular. Our algorithm ADT requires only that T be nonsingular. Both our algorithms for Toeplitz systems are derived from algorithms for computing entries in the Padé table for a given power series. We prove that entries in the Padé table can be computed by the Extended Euclidean Algorithm. We describe an algorithm EMGCD (Extended Middle Greatest Common Divisor) which is faster than the algorithm HGCD of Aho, Hopcroft and Ullman, although both require time O(n log²n), and we generalize EMGCD to produce PRSDC (Polynomial Remainder Sequence Divide and Conquer) which produces any iterate in the PRS, not just the middle term, in time O(n log²n). Applying PRSDC to the polynomials U₀(x) = x²ⁿ⁺¹ and U₁(x) = a₀ + a₁x + … + a_2nx²ⁿ gives algorithm AD (Anti-Diagonal), which computes any (m, p) entry along the antidiagonal m + p = 2n of the Padé table for U₁ in time O(n log²n). Our other algorithm, MD (Main-Diagonal), computes any diagonal entry (n, n) in the Padé table for a normal power series, also in time O(n log²n). MD is related to Schönhage's fast continued fraction algorithm. A Toeplitz matrix T is naturally associated with U₁, and the (n, n) Padé approximation to U₁ gives the first column of T^?1. We show how a formula due to Trench can be used to compute the solution z of Tz = b in time O(n log n) from the first row and column of T^?1. Thus, the Padé table algorithms AD and MD give O(n log²n) Toeplitz algorithms ADT and MDT. Trench's formula breaks down in certain degenerate cases, but in such cases a companion formula, the discrete analog of the Christoffel-Darboux formula, is valid and may be used to compute z in time O(n log²n) via the fast computation (by algorithm AD) of at most four Padé approximants. We also apply our results to obtain new complexity bounds for the solution of banded Toeplitz systems and for BCH decoding via Berlekamp's algorithm.     

Dynamic lot-sizing model for major and minor demands

This paper deals with a lot-sizing model for major and minor demands in which major demands are specified by time windows while minor demands are given by periods. For major demands, the agreeable time window structure is assumed where each time window is not strictly nested in any other time windows. To incorporate the economy of scale of large production quantity, especially from major demands, concave cost structure in production must be considered. Investigating the optimality properties, we propose optimal solution procedures based on dynamic program. For a simple case when only major demands exist, we propose an optimal procedure with running time of O(n²T)$\mathrm{O}(n^{2}T)$ where n is the number of demands and T   is the length of the planning horizon. Extending the algorithm to the model with major and minor demands, we propose an algorithm with complexity O(n²T²)$\mathrm{O}(n^2{T}^2)$.     

Quartic spline methods for solving one-dimensional telegraphic equations

In this paper, by using a quartic spline in space and generalized trapezoidal formula in time direction, one-dimensional telegraphic equations are solved. We present new classes of two-level schemes. The accuracy of these methods are O(k²+h⁴). It has been shown that by suitably choosing parameter, a high accuracy scheme of O(k³+h⁴) can be derived from our methods. Numerical results demonstrate the superiority of the new scheme.     

Factorizing symmetric indefinite matrices

The LDL^T factorization of a symmetric indefinite matrix, although efficient computationally, may not exist and can be unstable in the presence of round off error. The use of block diagonal 2×2 pivots is attractive, but there are some difficulties in determining an efficient and stable pivot strategy. Previous suggestions have required O(n>³) operations (either multiplications or comparisons) just to implement the pivot strategy. A new strategy is described which in practice only requires O(n²) operations. Indeed, the effort required by this pivot strategy is less than that required when using partial pivoting with an unsymmetric LU factorization, which is the usual way of factorizing indefinite matrices.     

A Two-Echelon Inventory Optimization Model with Demand Time Window Considerations

This paper studies a two-echelon dynamic lot-sizing model with demand time windows and early and late delivery penalties. The problem is motivated by third-party logistics and vendor managed inventory applications in the computer industry where delivery time windows are typically specified under a time definite delivery contract. Studying the optimality properties of the problem, the paper provides polynomial time algorithms that require O(T ³) computational complexity if backlogging is not allowed and O(T ⁵) computational complexity if backlogging is allowed.     

On the double commutant of Cowen-Douglas operators

Let T be a Cowen-Douglas operator. In this paper, we study the von Neumann algebra V^?(T) consisting of operators commuting with both T and T^? from a geometric viewpoint. We identify operators in V^?(T) with connection-preserving bundle maps on E(T), the holomorphic Hermitian vector bundle associated to T. By studying such bundle maps, the structure of V^?(T) as well as information on reducing subspaces of T can be determined.     

Zero density of L-functions related to Maass forms

Let f(z) be a Hecke-Maass cusp form for SL ₂(?), and let L(s, f) be the corresponding automorphic L-function associated to f. For sufficiently large T, let N(σ, T) be the number of zeros ρ = β +iγ of L(s, f) with |γ| ? T, β ? σ, the zeros being counted according to multiplicity. In this paper, we get that for 3/4 ? σ ? 1 ? ?, there exists a constant C = C(?) such that N(σ,T) ? T ^2(1?σ)/σ(logT) ^C , which improves the previous results.     

Efficient partition trees

We prove a theorem on partitioning point sets inE ^d (d fixed) and give an efficient construction of partition trees based on it. This yields a simplex range searching structure with linear space,O(n logn) deterministic preprocessing time, andO(n ^1?1/d (logn) ^O(1)) query time. WithO(nlogn) preprocessing time, where δ is an arbitrary positive constant, a more complicated data structure yields query timeO(n ^1?1/d (log logn) ^O(1)). This attains the lower bounds due to Chazelle [C1] up to polylogarithmic factors, improving and simplifying previous results of Chazelleet al. [CSW]. The partition result implies that, forr ^d≤n ^1?δ, a (1/r)-approximation of sizeO(r ^d) with respect to simplices for ann-point set inE ^d can be computed inO(n logr) deterministic time. A (1/r)-cutting of sizeO(r ^d) for a collection ofn hyperplanes inE ^d can be computed inO(n logr) deterministic time, provided thatr≤n ^1/(2d?1).     

Eigenvectors and cyclic vectors of bilateral weighted shifts. II: Simply invariant subspaces

Let T be an injective bilateral weighted shift onl ² thought as "multiplication by λ" on a space of formal Laurent series L²(β). (a) If L²(β) is contained in a space of quasi-analytic class of functions, then the point spectrum σ_p(T^?) of T^? contains a circle and the cyclic invariant subspaceM _f of T generated by f is simply invariant (i.e., ∩{(T^k M _f)^?: k ≥ 0}= {0}) for each f in L²(β); (b) If L²(β) contains a non-quasi-analytic class of functions (defined on a circle г) of a certain type related with the weight sequence of T, then there exists f in L²(ß) such thatM _f is a non-trivial doubly invariant subspace (i.e., (TM _f)^? =M _f); furthermore, if г ? σ_p(T^*), then σ_p (T^*) = г and f can be chosen so that σ_p([T∣M _f]^*) = г?{α}, for some α ε г. Several examples show that the gap between operators satisfying (a) and operators satisfying (b) is rather small.     

Superconvergence of Legendre projection methods for the eigenvalue problem of a compact integral operator

In this paper, we consider the Galerkin and collocation methods for the eigenvalue problem of a compact integral operator with a smooth kernel using the Legendre polynomials of degree ≤n. We prove that the error bounds for eigenvalues are of the order O(n^−2r) and the gap between the spectral subspaces are of the orders O(n^−r) in L₂-norm and O(n^1/2−r) in the infinity norm, where r denotes the smoothness of the kernel. By iterating the eigenvectors we show that the iterated eigenvectors converge with the orders of convergence O(n^−2r) in both L₂-norm and infinity norm. We illustrate our results with numerical examples.     

Enumeration aspects of maximal cliques and bicliques

We present a general framework to study enumeration algorithms for maximal cliques and maximal bicliques of a graph. Given a graph G, we introduce the notion of the transition graph T(G) whose vertices are maximal cliques of G and arcs are transitions between cliques. We show that T(G) is a strongly connected graph and characterize a rooted cover tree of T(G) which appears implicitly in [D.S. Johnson, M. Yannakakis, C.H. Papadimitriou, On generating all maximal independent sets, Information Processing Letters 27 (1988) 119-123; S. Tsukiyama, M. Ide, M. Aiyoshi, I. Shirawaka, A new algorithm for generating all the independent sets, SIAM Journal on Computing 6 (1977) 505-517]. When G is a bipartite graph, we show that the Galois lattice of G is a partial graph of T(G) and we deduce that algorithms based on the Galois lattice are a particular search of T(G). Moreover, we show that algorithms in [G. Alexe, S. Alexe, Y. Crama, S. Foldes, P.L. Hammer, B. Simeone, Consensus algorithms for the generation of all maximal bicliques, Discrete Applied Mathematics 145 (1) (2004) 11-21; L. Nourine, O. Raynaud, A fast algorithm for building lattices, Information Processing Letters 71 (1999) 199-204] generate maximal bicliques of a bipartite graph in O(n²) per maximal biclique, where n is the number of vertices in G. Finally, we show that under some specific numbering, the transition graph T(G) has a hamiltonian path for chordal and comparability graphs.     

An asymptotic formula for the primitive of Hardy’s function

Let Z(t) be the classical Hardy function in the theory of Riemann’s zeta-function. An asymptotic formula with an error term O(T ^1/6log?T) is given for the integral of Z(t) over the interval [0,T], with special attention paid to the critical cases when the fractional part of \(\sqrt{T/2\pi }\) is close to \(\frac{1}{4}\) or \(\frac{3}{4}\).     

Estimation of the Gauss–Markov process from observation of its sign

Let X(t) be the ergodic Gauss–Markov process with mean zero and covariance function e^?|τ|. Let D(t) be +1, 0 or ?1 according as X(t) is positive, zero or negative. We determine the non-linear estimator of X(t₁) based solely on D(t), ?T ? t ? 0, that has minimal mean–squared error ε²(t₁, T). We present formulae for ε²(t₁, T) and compare it numerically for a range of values of t₁ and T with the best linear estimator of X(t₁) based on the same data.     

Remarks on a displacement-rank inversion method for Toeplitz systems

Comments are made regarding the implementation of a Toeplitz-matrix inversion algorithm described by Bitmead and Anderson in [1]. We show that although the algorithm is asymptotically efficient with O(N(logN)²) operations, it requires a 10⁶×10⁶ matrix to break even with the class of algorithms whose operation count is of the order of O(N²) (as found in [4]).     

Ergodic Theory and Maximal Abelian Subalgebras of the Hyperfinite Factor

Let T be a free ergodic measure-preserving action of an abelian group G on (X,μ). The crossed product algebra R_T=L^∞(X,μ)? G has two distinguished masas, the image C_T of L^∞(X,μ) and the algebra S_T generated by the image of G. We conjecture that conjugacy of the singular masas S_T⁽¹⁾ and S_T⁽²⁾ for weakly mixing actions T⁽¹⁾ and T⁽²⁾ of different groups implies that the groups are isomorphic and the actions are conjugate with respect to this isomorphism. Our main result supporting this conjecture is that the conclusion is true under the additional assumption that the isomorphism γ : R_T⁽¹⁾→R_T⁽²⁾ such that γ(S_T⁽¹⁾)=S_T⁽²⁾ has the property that the Cartan subalgebras γ(C_T⁽¹⁾) and C_T⁽²⁾ of R_T⁽²⁾ are inner conjugate. We discuss a stronger conjecture about the structure of the automorphism group Aut(R_T,S_T), and a weaker one about entropy as a conjugacy invariant. We study also the Pukanszky and some related invariants of S_T, and show that they have a simple interpretation in terms of the spectral theory of the action T. It follows that essentially all values of the Pukanszky invariant are realized by the masas S_T, and there exist non-conjugate singular masas with the same Pukanszky invariant.     

Periodic solutions for a nonautonomous ordinary differential equation

We consider the nonautonomous differential equation of second order x^″+a(t)x−b(t)x²+c(t)x³=0, where a(t),b(t),c(t) are T-periodic functions. This is a biomathematical model of an aneurysm in the circle of Willis. We prove the existence of at least two positive T-periodic solutions for this equation, using coincidence degree theories.     

Lie algebras generated by bounded linear operators on Hilbert spaces

It is proved that the operator Lie algebra ε(T,T^∗) generated by a bounded linear operator T on Hilbert space H is finite-dimensional if and only if T=N+Q, N is a normal operator, [N,Q]=0, and dimA(Q,Q^∗)<+∞, where ε(T,T^∗) denotes the smallest Lie algebra containing T,T^∗, and A(Q,Q^∗) denotes the associative subalgebra of B(H) generated by Q,Q^∗. Moreover, we also give a sufficient and necessary condition for operators to generate finite-dimensional semi-simple Lie algebras. Finally, we prove that if ε(T,T^∗) is an ad-compact E-solvable Lie algebra, then T is a normal operator.