Effects of service disciplines inG/GI/s queueing systems

Transient extremal properties of some service disciplines are established in theG/GI/s queueing system for the minimization and maximization of the expectations of the Schur convex functions, convex symmetric functions and the sums of convex functions of the waiting times, response times, lag times and latenesses. When resequencing is required in the system, the FCFS and LCFS disciplines are shown to minimize and maximize, respectively, the expectations of any increasing functions of the end-to-end delays. All of these results are presented in terms of stochastic orderings. The paper concludes with extensions of the results to the stationary regime and to tandem as well as general queueing networks.This work was supported in part by the National Science Foundation under grant ASC 88-8802764.The work of this author was also partially supported by CEC DG-XIII under the ESPRIT-BRA grant QMIPS.     

Group Scheduling with Controllable Setup and Processing Times: Minimizing Total Weighted Completion Time

The following single machine scheduling problem is studied. A partition of a set of n jobs into g groups on the basis of group technology is given. The machine processes jobs of the same group contiguously, with a sequence independent setup time preceding the processing of each group. The setup times and the job processing times are controllable through the allocation of a continuously divisible or discrete resource to them. Each job uses the same amount of the resource. Each setup also uses the same amount of resource, which may be different from that for the jobs. Polynomial-time algorithms are constructed for variants of the problem of finding an optimal job sequence and resource values so as to minimize the total weighted job completion time, subject to given restrictions on resource consumption. The algorithms are based on a polynomial enumeration of the candidates for an optimal job sequence and solving the problem with a fixed job sequence by linear programming. This research was supported in part by The Hong Kong Polytechnic University under grant number G-T246 and the Research Grants Council of Hong Kong under grant number PolyU 5191/01E. In addition, the research of M.Y. Kovalyov was supported by INTAS under grant number 00-217.     

On multilevel iterative methods for optimization problems

This paper is concerned with multilevel iterative methods which combine a descent scheme with a hierarchy of auxiliary problems in lower dimensional subspaces. The construction of auxiliary problems as well as applications to elasto-plastic model and linear programming are described. The auxiliary problem for the dual of a perturbed linear program is interpreted as a dual of perturbed aggregated linear program. Coercivity of the objective function over the feasible set is sufficient for the boundedness of the iterates. Equivalents of this condition are presented in special cases.Supported by NSF under grant DMS-8704169, AFOSR under grant 86-0126, and ONR under Contract N00014-83-K-0104. Consulting for American Airlines Decision Technologies, MD 2C55, P.O. Box 619616, DFW, TX 75261-9616, USA.Supported by NSF under grant DMS-8704169 and AFOSR under grant 86-0126.     

Sample-path optimization of convex stochastic performance functions

In this paper we propose a method for optimizing convex performance functions in stochastic systems. These functions can include expected performance in static systems and steady-state performance in discrete-event dynamic systems; they may be nonsmooth. The method is closely related to retrospective simulation optimization; it appears to overcome some limitations of stochastic approximation, which is often applied to such problems. We explain the method and give computational results for two classes of problems: tandem production lines with up to 50 machines, and stochastic PERT (Program Evaluation and Review Technique) problems with up to 70 nodes and 110 arcs. Sponsored by the National Science Foundation under grant number CCR-9109345, by the Air Force Systems Command, USAF, under grant numbers F49620-93-1-0068 and F49620-95-1-0222, by the U.S. Army Research Office under grant number DAAL03-92-G-0408, and by the U.S. Army Space and Strategic Defense Command under contract number DASG60-91-C-0144. The U.S. Government has certain rights in this material, and is authorized to reproduce and distribute reprints for Governmental purposes notwithstanding any copyright notation thereon. Sponsored by a Wisconsin/Hilldale Research Award, by the U.S. Army Space and Strategic Defense Command under contract number DASG60-91-C-0144, and the Air Force Systems Command, USAF, under grant number F49620-93-1-0068. Sponsored by the National Science Foundation under grant number DDM-9201813.     

The Theory of Multidimensional Persistence

Persistent homology captures the topology of a filtration—a one-parameter family of increasing spaces—in terms of a complete discrete invariant. This invariant is a multiset of intervals that denote the lifetimes of the topological entities within the filtration. In many applications of topology, we need to study a multifiltration: a family of spaces parameterized along multiple geometric dimensions. In this paper, we show that no similar complete discrete invariant exists for multidimensional persistence. Instead, we propose the rank invariant, a discrete invariant for the robust estimation of Betti numbers in a multifiltration, and prove its completeness in one dimension. The first author was partially supported by NSF under grant DMS-0354543. The second author was partially supported by DARPA under grant HR 0011-06-1-0038 and by ONR under grant N 00014-08-1-0908. Both authors were partially supported by DARPA under grant HR 0011-05-1-0007.     

Error bounds for minimal energy bivariate polynomial splines

Summary. We derive error bounds for bivariate spline interpolants which are calculated by minimizing certain natural energy norms. Received March 28, 2000 / Revised version received June 23, 2000 / Published online March 8, 2002 RID="*" ID="*" Supported by the National Science Foundation under grant DMS-9870187 RID="**" ID="**" Supported by the National Science Foundation under grant DMS-9803340 and by the Army Research Office under grant DAAD-19-99-1-0160     

On computing the center of a convex quadratically constrained set

We propose a method for finding analytic center of a convex feasible region whose boundaries are defined by quadratic functions. The algorithm starts from an arbitrary initial point and approaches to the desired center by simultaneously reducing infeasibility or slackness of all constraints. A partial Newton step is taken at each iteration.Research supported in part by the ONR under grant N00014-87-K-0214 and by the NSF under grant CCR-8810107.Research supported in part by the NSF under grant ECS-8721709.     

The number of periodic solutions of polynomial differential equations

We estimate the number of periodic solutions for special classes ofnth-order ordinary differential equations with variable coefficients. Translated fromMatematicheskie Zametki, Vol. 64, No. 5, pp. 720–727, November, 1998. The author thanks Yu. S. Il'yashenko for setting the problems, permanent advice, and overall support. The author is also thankful to D. A. Panov for numerous discussions. This research was supported by the CRDF Foundation under grant MR1-220, by the INTAS Foundation under grant No. 93-05-07, and by the Russian Foundation for Basic Research under grant No. 95-01-01258.     

Every arrangement extends to a spread

Supported in part by NSA grant MDA904-89-H-2038, PSC-CUNY grant 662330, and the Center for Discrete Mathematics and Theoretical Computer Science (DIMACS), a National Science Foundation Science and Technology Center under NSF grant STC88-09648.     

CD(4) has bounded width

We prove that the constraint languages invariant under a short sequence of Jónsson terms (containing at most three non-trivial ternary terms) are tractable by showing that they have bounded width. This improves a previous result by Kiss and Valeriote and presents some evidence that the Larose–Zádori conjecture holds in the congruence-distributive case. The first author was supported by EPSRC grant EP/C54384X/1. The second author was supported by the MEC under grant TIN 2006-15387-C03-03, the EU PASCAL Network of Excellence IST-2002-506778, and the MODNET Marie Curie Research Training Network MRTN-CT-2004-512234. The third author was supported by grant no. 144011G of the Ministry of Science and Environment of Serbia. The fourth author was partially supported by the Hungarian National Foundation for Scientific Research (OTKA), grant nos. T 48809 and K 60148.     

Denumerable controlled Markov chains with average reward criterion: Sample path optimality

We consider discrete-time nonlinear controlled stochastic systems, modeled by controlled Makov chains with denumerable state space and compact action space. The corresponding stochastic control problem of maximizing average rewards in the long-run is studied. Departing from the most common position which usesexpected values of rewards, we focus on a sample path analysis of the stream of states/rewards. Under a Lyapunov function condition, we show that stationary policies obtained from the average reward optimality equation are not only average reward optimal, but indeed sample path average reward optimal, for almost all sample paths.Research supported by a U.S.-México Collaborative Research Program funded by the National Science Foundation under grant NSF-INT 9201430, and by CONACyT-MEXICO.Partially supported by the MAXTOR Foundation for applied Probability and Statistics, under grant No. 01-01-56/04-93.Research partially supported by the Engineering Foundation under grant RI-A-93-10, and by a grant from the AT&T Foundation.     

On the spectra of sums of orthogonal projections with applications to parallel computing

Many parallel iterative algorithms for solving symmetric, positive definite problems proceed by solving in each iteration, a number of independent systems on subspaces. The convergence of such methods is determined by the spectrum of the sums of orthogonal projections on those subspaces, while the convergence of a related sequential method is determined by the spectrum of the product of complementary projections. We study spectral properties of sums of orthogonal projections and in the case of two projections, characterize the spectrum of the sum completely in terms of the spectrum of the product.This work was supported in part by the Norwegian Research Council for Science and the Humanities under grant D.01.08.054 and by The Royal Norwegian Council for Scientific and Industrial Research under grant IT2.28.28484; also supported in part by the Air Force Office of Scientific Research under grant AFOSR-86-0126 and by the National Science Foundation under grant DMS-8704169.     

Implementation of a continuation method for normal maps

This paper presents an implementation of a nonsmooth continuation method of which the idea was originally put forward by Alexander et al. We show how the method can be computationally implemented and present numerical results for variational inequality problems in up to 96 variables. The research reported here was sponsored by the Air Force Office of Scientific Research, Air Force Materiel Command, USAF, under grant numbers F49620-93-1-0068 and F49620-95-1-0222, by the U.S. Army Research Office under grant number DAAH04-95-1-0149, and by the National Science Foundation under grant number CCR-9109345. The U.S. Government has certain rights in this material, and is authorized to reproduce and distribute reprints for Governmental purposes notwithstanding any copyright notation thereon. The views and conclusions contained herein are those of the authors and should not be interpreted as necessarily representing the official policies or endorsements, either expressed or implied, of the sponsoring agencies or the U.S. Government.     

Wachspress type rational complex planar splines of degree (3,1)

We study the existence, uniqueness and approximation properties of rational complex planar spline interpolants of order (3, 1). We also find sufficient conditions for such interpolants to be quasiregular and quasiconformal. Examples are given. This work was carried out with the aid of MACSYMA, a large symbolic manipulation program developed at the MIT Laboratory for Computer Science and supported from 1975 to 1983 by the National Aeronautics and Space Administration under grant NSG 1323, by the Office of Naval Research under grant N00014-77C-0641, by the U.S. Department of Energy under grant ET-78-C-024687, and by the U.S. Air Force under grant F49620-79-C-020, and since 1982 by Symbolics, Inc. of Burlington, MA.     

Dynamic lot-sizing problem with demand time windows and container-based transportation cost

In this paper, we study the dynamic lot-sizing problem with demand time windows and container-based transportation cost. For each particular demand, there are corresponding earliest and latest times, and the duration between such earliest and latest times is the demand time window. If a demand is satisfied by a delivery within demand time window, then there is no holding or backlogging cost incurred. Our purpose is to satisfy demand at a minimum total cost, including setup cost, procurement cost, container cost, and inventory holding cost. This research is supported in part by Hong Kong RGC grant HKUST 6010/02E and NUS ARF grant R-266-000-019-112.     

Differentiability of convex measures

In this paper we consider convex measures on finite-dimensional spaces. We prove the differentiability of convex measures in the Skorokhod sense (and under some natural conditions, in the Fomin sense also). Simultaneously we give some additional results on differentiability of convex measures.Translated fromMatematicheskie Zametki, Vol. 58, No. 6, pp. 862–871, December, 1995.This research was partially supported by the Russian Foundation for Basic Research under grant No. 94-01-01556, by the Ministry of Science under grant No. M38300 and by the International Science Foundation under grant No. M38000.     

On the convergence of Newton iterations to non-stationary points

We study conditions under which line search Newton methods for nonlinear systems of equations and optimization fail due to the presence of singular non-stationary points. These points are not solutions of the problem and are characterized by the fact that Jacobian or Hessian matrices are singular. It is shown that, for systems of nonlinear equations, the interaction between the Newton direction and the merit function can prevent the iterates from escaping such non-stationary points. The unconstrained minimization problem is also studied, and conditions under which false convergence cannot occur are presented. Several examples illustrating failure of Newton iterations for constrained optimization are also presented. The paper also shows that a class of line search feasible interior methods cannot exhibit convergence to non-stationary points. This author was supported by Air Force Office of Scientific Research grant F49620-00-1-0162, Army Research Office Grant DAAG55-98-1-0176, and National Science Foundation grant INT-9726199.This author was supported by Department of Energy grant DE-FG02-87ER25047-A004.This author was supported by National Science Foundation grant CCR-9987818 and Department of Energy grant DE-FG02-87ER25047-A004.     

Local convergence of interior-point algorithms for degenerate monotone LCP

Most asymptotic convergence analysis of interior-point algorithms for monotone linear complementarity problems assumes that the problem is nondegenerate, that is, the solution set contains a strictly complementary solution. We investigate the behavior of these algorithms when this assumption is removed.The work of this author was based on research supported by the National Science Foundation under grant DDM-9109404 and the Office of Naval Research under grant N00014-93-1-0234.The work of this author was based on research supported by the Office of Scientific Computing, U.S. Department of Energy, under Contract W-31-109-Eng-38.     

Bi-Lipschitz geometry of weighted homogeneous surface singularities

We show that a weighted homogeneous complex surface singularity is metrically conical (i.e., bi-Lipschitz equivalent to a metric cone) only if its two lowest weights are equal. We also give an example of a pair of weighted homogeneous complex surface singularities that are topologically equivalent but not bi-Lipschitz equivalent. L. Birbrair was supported under CNPq grant no. 300985/93-2. A. Fernandes was supported under CNPq grant no. 300393/2005-9. W. D. Neumann was supported under NSA grant H98230-06-1-011 and NSF grant no. DMS-0206464.