Application of average dynamic programming to inventory systems

We show the existence ofaverage cost (AC-) optimal policy for an inventory system withuncountable state space; in fact, the AC-optimal cost and an AC-optimal stationary policy areexplicitly computed. In order to do this, we use a variant of thevanishing discount factor approach, which have been intensively studied in recent years but the available results not cover the inventory problem we are interested in.The work of the first author (OVA) was partially supported by Fondo del Sistema de Investigación del Mar de Cortéz under grant SIMAC/94/CT-005. The work of the second author (RMdO) was partially supported by Consejo Nacional de Ciencia y Tecnologia (CONACyT) under grant 0635P-E9506.     

Value iteration in average cost Markov control processes on Borel spaces

This paper deals with discrete-time Markov control processes withBorel state and control spaces, with possiblyunbounded costs andnoncompact control constraint sets, and the average cost criterion. Conditions are given for the convergence of the value iteration algorithm to the optimal average cost, and for a sequence of finite-horizon optimal policies to have an accumulation point which is average cost optimal.This research was partially supported by the Consejo Nacional de Ciencia y Tecnología (CONACyT) under grant 1332-E9206.     

Single-Machine Scheduling with Exponential Processing Times and General Stochastic Cost Functions

We study a single-machine stochastic scheduling problem with n jobs, in which each job has a random processing time and a general stochastic cost function which may include a random due date and weight. The processing times are exponentially distributed, whereas the stochastic cost functions and the due dates may follow any distributions. The objective is to minimize the expected sum of the cost functions. We prove that a sequence in an order based on the product of the rate of processing time with the expected cost function is optimal, and under certain conditions, a sequence with the weighted shortest expected processing time first (WSEPT) structure is optimal. We show that this generalizes previous known results to more general situations. Examples of applications to practical problems are also discussed.This work was partially supported by the Research Grants Council of Hong Kong under Earmarked Grants No. CUHK4418/99E and No. PolyU 5081/00E.     

Packing directed circuits

We prove a conjecture of Younger, that for every integern0 there exists an integert0 such that for every digraphG, eitherG hasn vertex-disjoint directed circuits, orG can be made acyclic by deleting at mostt vertices.Research partially supported by DONET ECHM contract CHRXCT930090.Research partially supported by DIMACS, by NSF grant DMS-9401981 and by ONR grant N00014-92-J-1965, and partially performed under a consulting agreement with Bellcore.Research partially supported by DIMACS, by Université de Paris VI, by NSF grant DMS-9303761 and by ONR grant N00014-93-1-0325, and partially performed under a consulting agreement with Bellcore.     

The linear quadratic optimal control problem for hereditary differential systems: Theory and numerical solution

In the first part of this paper, we summarize and complete earlier results of Delfour-Mitter [3] on the optimal control problem for linear hereditary differential systems (HDS) with a linear-quadratic cost function. The properties of the operator (t) which characterizes the feedback gains and the reference functionr(t) are fully detailed. In a second part, we construct an approximation to the linear HDS in state form and to the linear adjoint state equation and prove convergence. In a third part we construct and solve the approximate optimal control problem following the method of J. C. Nédelec. In the last part we construct the approximation to (t) andr(t) and prove convergence. Finally we give a number of typical examples to illustrate the main features of the kernel of (t).This research was supported in part by National Research Council (Canada) Grant A8730 and by a Subvention F.C.A.C. du Ministère de l'Education du Québec at the Centre de Recherches Mathématiques, Université de Montréal, Montréal, Québec, Canada.     

On the approximate solution of time-optimal control problems

In this paper we are concerned with the approximate solution of time-optimal control problems in a nonreflexive Banach SpaceE by sequences of similar problems in Banach spacesE _n which are assumed to approximateE in a fairly general sense. The problems under consideration are such that the solution operator of the associated evolution equation is a strongly continuous holomorphic contraction semigroup and the class of controls is taken from the dual of the Phillips adjoint space with respect to the infinitesimal generator of that semigroup. The main object is to establish convergence of optimal controls, transition times and corresponding trajectories of the approximating control problems which can be done by means of some results from the theory of approximation of semigroups of operators. Finally, these abstract convergence results will be applied to time-optimal control problems arising from heat transfer and diffusion processes.Research supported in part by the Deutsche Forschungsgemeinschaft (DFG)     

Average search and update costs in skip lists

Skip lists, introduced by Pugh, provide an alternative to search trees, although a precise analysis of their behaviour had been elusive. The exact value of the expected cost for the search of themth element in a skip list ofn elements is derived first in terms of previously studied functions, and secondly as an asymptotic expression. The latter suggests that Pugh's upper bound of the expected search cost is fairly tight for the interesting cases. Assuming a uniform query distribution, the exact and an asymptotic value of the average (over allm) expected search cost in a skip list ofn elements is also derived. Finally, all insert and delete costs are obtained.This research was supported in part by the Natural Science and Engineering Research Council of Canada under grant No. A-8237, the Information Technology Research Centre of Ontario, and FON-DECYT (Chile) under grant 91-1252.     

Boundary control of parabolic systems: Finite-element approximation

Finite-element approximation of a Dirichlet type boundary control problem for parabolic systems is considered. An approach based on the direct approximation of an input-output semigroup formula is applied. Error estimates inL ₂[OT; L ₂()] andL ₂[OT; L ₂()] norms are derived for optimal state and optimal control, respectively. It turns out that these estimates areoptimal with respect to the approximation theoretic properties.Research supported in part under Grant no. NSG 4015, National Aeronautics and Space Administration.     

Probabilistic aspects of finite-fuel,reflected follower problems

The issue is that of following the path of a Brownian particle by a process of bounded total variation and subject to a reflecting barrier at the origin, in such a way as to minimize expected total cost over a finite horizon. We establish the existence of optimal processes and the dynamic programming equations for this question, and show (by purely probabilistic arguments) its relation to an appropriatefamily of optimal stopping problems with absorption at the origin.Work carried out during a visit by the second author at the University Pierre et Marie Curie (Paris VI), and at INRIA (Institut National de Recherche en Informatique et en Automatique). The hospitality of these institutions is gratefully acknowledged.Research supported in part by the U.S. Air Force Office of Scientific Research, under grant AFOSR-86-0203.     

Single-machine scheduling to minimize earliness and number of tardy jobs

This paper considers the problem of assigning a common due-date to a set of simultaneously available jobs and sequencing them on a single machine. The objective is to determine the optimal combination of the common due-date and job sequence that minimizes a cost function based on the assigned due-date, job earliness values, and number of tardy jobs. It is shown that the optimal due-date coincides with one of the job completion times. Conditions are derived to determine the optimal number of nontardy jobs. It is also shown that the optimal job sequence is one in which the nontardy jobs are arranged in nonincreasing order of processing times. An efficient algorithm of O(n logn) time complexity to find the optimal solution is presented and an illustrative example is provided. Finally, several extensions of the model are discussed.This research was supported in part by the Natural Sciences and Engineering Research Council of Canada under Grant OPG0036424. The authors are thankful to two anonymous referees for their constructive comments.     

Adaptive control of Markov processes with incomplete state information and unknown parameters

Recent results for parameter-adaptive Markov decision processes (MDP's) are extended to partially observed MDP's depending on unknown parameters. These results include approximations converging uniformly to the optimal reward function and asymptotically optimal adaptive policies.This research was supported in part by the Consejo del Sistema Nacional de Educación Tecnologica (COSNET) under Grant 178/84, in part by the Air Force Office of Scientific Research under Grant AFOSR-84-0089, in part by the National Science Foundation under Grant ECS-84-12100, and in part by the Joint Services Electronics Program under Contract F49602-82-C-0033.     

Parallel comparison algorithms for approximation problems

Suppose we haven elements from a totally ordered domain, and we are allowed to performp parallel comparisons in each time unit (=round). In this paper we determine, up to a constant factor, the time complexity of several approximation problems in the common parallel comparison tree model of Valiant, for all admissible values ofn, p and , where is an accuracy parameter determining the quality of the required approximation. The problems considered include the approximate maximum problem, approximate sorting and approximate merging. Our results imply as special cases, all the known results about the time complexity for parallel sorting, parallel merging and parallel selection of the maximum (in the comparison model), up to a constant factor. We mention one very special but representative result concerning the approximate maximum problem; suppose we wish to find, among the givenn elements, one which belongs to the biggestn/2, where in each round we are allowed to askn binary comparisons. We show that log^* n+O(1) rounds are both necessary and sufficient in the best algorithm for this problem.Research supported in part by Allon Fellowship, by a Bat Sheva de Rothschild grant and by the Fund for Basic Research administered by the Israel Academy of Sciences.     

Fast computation in adaptive tree approximation

Summary. Adaptive methods of approximation arise in many settings including numerical methods for PDEs and image processing. They can usually be described by a tree which records the adaptive decisions. This paper is concerned with the fast computation of near optimal trees based on n adaptive decisions. The best tree based on n adaptive decisions could be found by examining all such possibilities. However, this is exponential in n and could be numerically prohibitive. The main result of this paper is to show that it is possible to find near optimal trees using computations linear in n.Mathematics Subject Classification (2000): 65Y20, 65N50, 41A63, 41A15, 68W40, 68W25This work has been supported in part by the Office of Naval Research contracts 03-10051, (N00014-00-1-0470), the Army Research Office contract DAAD 19-02-1-0028, and the National Science Foundation grants DMS 9872890, DMS 0221642.     

An optimal lower bound on the number of variables for graph identification

In this paper we show that (n) variables are needed for first-order logic with counting to identify graphs onn vertices. Thek-variable language with counting is equivalent to the (k–1)-dimensional Weisfeiler-Lehman method. We thus settle a long-standing open problem. Previously it was an open question whether or not 4 variables suffice. Our lower bound remains true over a set of graphs of color class size 4. This contrasts sharply with the fact that 3 variables suffice to identify all graphs of color class size 3, and 2 variables suffice to identify almost all graphs. Our lower bound is optimal up to multiplication by a constant becausen variables obviously suffice to identify graphs onn vertices.Research supported by NSF grant CCR-8709818.Research supported by NSF grant CCR-8805978 and Pennsylvania State University Research Initiation grant 428-45.Research supported by NSF grants DCR-8603346 and CCR-8806308.     

The central limit theorem for Carleman’s equation

The purpose of this paper is to discuss the analogy between the law of large numbers and the central limit theorem of classical probability theory on the one hand and the hydrodynamical approximations in the statistical mechanics of gases on the other. The chief illustration is provided by Carleman's model [2] for which the central limit approximation is a kind of non-linear Brownian motion regulated by ∂n/∂t=(n'/n)^′. Research supported by the National Science Foundation under NSF Grant NSF-GP-37069X1.     

Generating combinations in parallel

A parallel algorithm for generating all combinations ofm out ofn items in lexicographic order is presented. The algorithm usesm processors and runs inO(nCm) time. The cost of the algorithm, which is the parallel running time multiplied by the number of processors used, is optimal to within a constant multiplicative factor in view of the (ncm*m) lower bound on the number of operations required to solve this problem using a sequential computer.This work was supported by the Natural Sciences and Engineering Research Council of Canada under Grant NSERC-A3336.     

A criterion for uniqueness of a critical point inH 2 rational approximation

This paper presents a criterion for uniqueness of a critical point inH _2,R rational approximation of type (m, n), withm≥n-1. This criterion is differential-topological in nature, and turns out to be connected with corona equations and classical interpolation theory. We illustrate its use with three examples, namely best approximation of fixed type on small circles, a de Montessus de Ballore type theorem, and diagonal, approximation to the exponential function of large degree. The research of this author was supported, in part, by NSF-INRIA cooperative research grant INT-9417234 as well as NSF grant DMS-9501130.     

Approximations and computational methods for Optimal Stopping and Stochastic Impulsive Control problems

The paper treats a computational method for the Optimal Stopping and Stochastic Impulsive Control problem for a diffusion. In the latter problem control acts only intermittently since there is a basic positive transaction cost to be paid at each instant that the control acts. For eachh > 0, a controlled Markov chain is constructed, whose continuous time interpolations are a natural approximation to the diffusion, for both the optimal stopping and impulsive control situations. The solutions to the optimal stopping and impulsive control problems for the chains are relatively easy to obtain by using standard procedures, and they converge to the solutions of the corresponding problems for the diffusion models ash0.Research was supported in part by the Air Force Office of Scientific Research AF-AFOSR 71-2078C, in part by the National Science Foundation GK 40493X and in part by the Office of Naval Research NONR N00014-67-A-0191-001804.     

Decay rates at low and high frequencies for a plate equation with feedback concentrated in interior curves

In this paper we study the stabilization of plate vibrations by means of piezoelectric actuators. In this situation the geometric control condition of Bardos, Lebeau and Rauch [6] is not satisfied. We prove that we have exponential stability for the low frequencies but not for the high frequencies. We give an explicit decay rate for regular initial data at high frequencies while clarifying the behavior of the constant which intervenes in this estimation there function of the frequency of cut n. The method used is based on some trace regularity which reduces stability to some observability inequalities for the corresponding undamped problem. Moreover, we show numerically at low frequencies, that the optimal location of the actuator is the center of the domain Ω. Research supported by the RIP program of Oberwolfach Institut and by the Tunisian Ministry for Scientific Research and Technology (MRST) under Grant 02/UR/15-01. Research supported by the RIP program of Oberwolfach Institut. (Received: September 17, 2003; revised: February 26, 2004)