Look-back policies for two-stage,pull-type production/inventory systems

We consider a two-stage, pull-type production/inventory system with a known service mechanism at the first stage. Set-ups and start-ups are involved in the operation of the second stage. We develop a production control policy for the second stage, within the class of (R, r) continuous-review policies, that minimizes the long run average total cost. We use a semi-Markov decision model to obtain an optimal policy for the operation of the second stage. The structure of the optimal policy suggests the use of a suboptimal look-back policy that delays the set-up at the second stage if the buffer lacks sufficient raw material. The performance of the system and the average total cost under the suboptimal policy can be obtained approximately using a decomposition algorithm. We show examples justifying the use of this suboptimal policy.This research is supported by the NSF Grant No. NSF-NCR-9110105, NSF Grant No. NSF-DDM-9014868 and by the North Atlantic Treaty Organization Grant No. NATO-CRG-900580.     

Boundary controllability of a linear semi-discrete 1-D wave equation derived from a mixed finite element method

In this article one discusses the controllability of a semi-discrete system obtained by discretizing in space the linear 1-D wave equation with a boundary control at one extremity. It is known that the semi-discrete models obtained with finite difference or the classical finite element method are not uniformly controllable as the discretization parameter h goes to zero (see [8]). Here we introduce a new semi-discrete model based on a mixed finite element method with two different basis functions for the position and velocity. We show that the controls obtained with these semi-discrete systems can be chosen uniformly bounded in L²(0,T) and in such a way that they converge to the HUM control of the continuous wave equation, i.e. the minimal L²-norm control. We illustrate the mathematical results with several numerical experiments. Supported by Grant BFM 2002-03345 of MCYT (Spain) and the TMR projects of the EU ``Homogenization and Multiple Scales" and ``New materials, adaptive systems and their nonlinearities: modelling, control and numerical simulations". Partially Supported by Grant BFM 2002-03345 of MCYT (Spain), Grant 17 of Egide-Brancusi Program and Grant 80/2005 of CNCSIS (Romania).     

Embedding of Hyperbolic Spaces in the Product of Trees

We show that for each n ≥ 2 there is a quasi-isometric embedding of the hyperbolic space Hⁿ in the product Tⁿ=T × ··· × T of n copies of a (simplicial) metric tree T. On the other hand, we prove that there is no quasi-isometric embedding for any metric tree T and any m ≥ 0.Mathematics Subject classification (2000). 54Exx.Supported by RFFI Grant 02-01-00090, CRDF Grant RMI-2381-ST-02 and SNF Grant 20-668 33.01. Supported by Swiss National Science Foundation.     

Semicontinuous solutions for Hamilton-Jacobi equations and theL ∞control problem

We prove uniqueness for extended real-valued lower semicontinuous viscosity solutions of the Bellman equation forL -control problems. This result is then used to prove uniqueness for lsc solutions of Hamilton-Jacobi equations of the form –u _t +H(t, x, u, –Du)=0, whereH(t, x, r, p) is convex inp. The remaining assumptions onH in the variablesr andp extend the currently known results.Supported in part by Grant DMS-9300805 from the National Science Foundation.     

The minimum independence number for designs

Fort=2,3 andk2t–1 we prove the existence oft–(n,k,) designs with independence numberC _,k n ^{(k–t)/(k–1)} (ln n) ^1/(k–1) . This is, up to the constant factor, the best possible.Some other related results are considered.Supported by NSF Grant DMS-9011850     

Competitive Algorithms for Relaxed List Update and Multilevel Caching

We study relaxed list update problem (RLUP), in which access requests are made to items stored in a list. The cost to access the jth item x_j is c_j, where c_i ≤ c_{i + 1} for all i. After the access, x_j can be repeatedly swapped, at no cost, with any item that precedes it in the list. This problem was introduced by Aggarwal et al. (1987, “Proc. 19th Symp. Theory of Computing,” pp. 305–313) as a model for the management of hierarchical memory that consists of a number of caches of increasing size and access time. They also proved that a version of LRU is C-competitive, for some C, for a restricted class of cost functions. We give an efficient offline algorithm that computes the optimal strategy for RLUP. We also show an elegant characterization of work functions for RLUP. We prove that move-to-front (MTF) is optimally competitive for RLUP with any cost function. An interesting feature of the proof is that it does not involve any estimates on the competitive ratio. Finally, we give a lower bound on the competitive ratio of online algorithms for RLUP.     

EfficientL 2 approximation by splines

LetS _N ^k (t) be the linear space ofk-th order splines on [0, 1] having the simple knotst _i determined from a fixed functiont by the rulet _i=t(i/N). In this paper we introduce sequences of operators {Q _N } _N =1 fromC ^k [0, 1] toS _N ^k (t) which are computationally simple and which, asN, give essentially the best possible approximations tof and its firstk–1 derivatives, in the norm ofL ₂[0, 1]. Precisely, we show thatN ^k–1((f–Q _N f) ⁱ –dist₂(f ⁽¹⁾,S _N ^k–1 (t)))0 fori=0, 1, ...,k–1. Several numerical examples are given.The research of this author was partially supported by the National Science Foundation under Grant MCS-77-02464The research of this author was partially supported by the U.S. Army Reesearch Office under Grant No. DAHC04-75-G-0816     

Planar configurations which determine few slopes

P. R. Scott conjectured, and Peter Ungar recently proved, that n noncollinear points in the plane determine at least n–1 slopes. This paper describes and characterizes the four known infinite classes of configurations where this minimum is achieved.Supported in part by NSF Grant MCS-80-02543 and NSF Epscor Grant IPS-80-11451     

K-Theory and analytic isomorphisms

Ifs is a central nonzerodivisor of a ringA, letB denote thes-adic completion ofA. By a theorem of Karoubi, there is a long exact sequence relating theK-theory ofA, B, A[s ^–1], andB[s ^–1]. This sequence was first exploited by Vorst in his thesis. We give two applications of the Karoubi sequence: (1) an example of a 2-dimensional normal domain withNK ₀0, answering a question of Murthy, and (2) a complete computation ofK ₂ of an (affine) seminormal curve over an algebraically closed field.Supported by NSF Grant MCS-79-03537     

Index theory on locally homogeneous spaces

We describe how the equivariant K homology class of an invariant elliptic operator on a homogeneous space of a linear semisimple Lie group determines the L ²-index of the associated operator on a finite volume locally homogeneous space. The machinery of equivariant K homology and of KK theory can be used to prove theorems about L ²-indices. We give an application motivated by the problem of calculating multiplicities of subrepresentations of quasi-regular representations.Supported by the National Science Foundation under Grant No. DMS-8903472.Supported by the National Science Foundation under Grant No. DMS-8901436.     

The excess of complex Hadamard matrices

A complex Hadamard matrix,C, of ordern has elements 1, –1,i, –i and satisfiesCC ^*=nI_nwhereC ^* denotes the conjugate transpose ofC. LetC=[c _ij] be a complex Hadamard matrix of order is called the sum ofC. (C)=|S(C)| is called the excess ofC. We study the excess of complex Hadamard matrices. As an application many real Hadamard matrices of large and maximal excess are obtained.Supported by an NSERC grant.Supported by Telecom grant 7027, an ATERB and ARC grant # A48830241.     

Infinite spectra in the first order theory of graphs

The psectrum Spec(A) of a sentenceA is, roughly, the set of those a for whichA has a threshold function at or nearp=n ^–a . Examples are given ofA with infinite spectra and with spectra of order type ⁱ for arbitraryi.     

Quotient algebras of Stanley-Reisner rings and local cohomology

We study certain subcomplexes Δ′ of an arbitrary simplicial complex Δ such that H_mⁱ(k[Δ])-H_mⁱ(k[Δ′]) for any 0i<dim(k[Δ′]). Here, H_mⁱ(k[Δ]) is the ith local cohomology module of the Stanley-Reisner ring k[Δ] of Δ over a field k. Our technique is an elegant approach to one of the most generalized versions of the rank selection theorems of J. Munkres (1984, Michigan Math. J.31, 113–128, Theorem 6.4) and R. Stanley (1979, Trans. Amer. Math. Soc.249, 139–157, Theorem 4.3).     

Admission control with batch arrivals

We consider the problem of dynamic admission control in a multi-class Markovian loss system receiving random batches, where each admitted class-i job demands an exponential service with rate μ, and brings a reward r_i. We show that the optimal admission policy is a sequential threshold policy with monotone thresholds.     

On Recognition by Spectrum of Finite Simple Linear Groups over Fields of Characteristic 2

A finite group G is said to be recognizable by spectrum, i.e., by the set of element orders, if every finite group H having the same spectrum as G is isomorphic to G. We prove that the simple linear groups L _n (2^k) are recognizable by spectrum for n = 2^m ≥ 32.Original Russian Text Copyright © 2005 Vasil’ev A. V. and Grechkoseeva M. A.The authors were supported by the Russian Foundation for Basic Research (Grant 05-01-00797), the State Maintenance Program for the Leading Scientific Schools of the Russian Federation (Grant NSh-2069.2003.1), the Program “ Development of the Scientific Potential of Higher School” of the Ministry for Education of the Russian Federation (Grant 8294), the Program “Universities of Russia” (Grant UR.04.01.202), and a grant of the Presidium of the Siberian Branch of the Russian Academy of Sciences (No. 86-197).__________Translated from Sibirskii Matematicheskii Zhurnal, Vol. 46, No. 4, pp. 749–758, July–August, 2005.     

Counting cycles and finite dimensional L norms

We obtain sharp bounds for the number of n-cycles in a finite graph as a function of the number of edges, and prove that the complete graph is optimal in more ways than could be imagined. We prove sharp estimates on both ∑_i=1ⁿx_i^k and ∑_i=1ⁿ|x_i|^k, subject to the constraints that ∑_i=1ⁿx_i²=C and ∑_i=1ⁿx_i=0.     

Strong approximation of additive functionals

LetX ₁,X ₂,...be a sequence of i.i.d. random variables and putS ₀=0,S _n =X ₁+...+X _n . A strong approximation type result is given forA _N = _i=1 ^N f(S _i ) whereF(x),xR is a real valued function. A similar result is given for ₀ ^t g(B(s))ds. Some weak convergence type implications are also discussed.1991 Mathematics Subject Classification: Primary: 60F15, Secondary: 60J15.Supported by the Hungarian National Foundation for Scientific Research, Grant No. 1905.Supported by an NSERC Canada Grant at Carleton University.Supported by a PSC CUNY Grant No.662349.     

Geometric convergence to e−z by rational functions with real poles

Summary In this paper, we show that there exists a sequence of rational functions of the formR _n(z)=p_n–1(z)/(1+z/n)ⁿ,n=1, 2, ..., with degp _n–1n–1, which converges geometrically toe ^–z in the uniform norm on [0, +), as well as on some infinite sector symmetric about the positive real axis. We also discuss the usefulness of such rational functions in approximating the solutions of heat-conduction type problems.Research supported in part by the Air Force Office of Scientific Research under Grant AFOSR-74-2688, and by the University of South Florida Research Council.Research supported in part by the Air Force Office of Scientific Research under Grant AFOSR-74-2729, and by the Energy Research and Development Administration (ERDA) under Grant E(11-1)-2075.     

Critical points for least-squares problems involving certain analytic functions,with applications to sigmoidal nets

This paper deals with nonlinear least-squares problems involving the fitting to data of parameterized analytic functions. For generic regression data, a general result establishes the countability, and under stronger assumptions finiteness, of the set of functions giving rise to critical points of the quadratic loss function. In the special case of what are usually called single-hidden layer neural networks, which are built upon the standard sigmoidal activation tanh(x) (or equivalently (1 +e ^–x )^–1), a rough upper bound for this cardinality is provided as well.Supported in part by US Air Force Grant AFOSR-94-0293.