Single Supplier Scheduling for Multiple Deliveries

The problem of scheduling the production and delivery of a supplier to feed the production of F manufacturers is studied. The orders fulfilled by the supplier are delivered to the manufacturers in batches of the same size. The supplier's production line has to be set up whenever it switches from processing an order of one manufacturer to an order of another manufacturer. The objective is to minimize the total setup cost, subject to maintaining continuous production for all manufacturers. The problem is proved to be NP-hard. It is reduced to a single machine scheduling problem with deadlines and jobs belonging to F part types. An O(NlogF) algorithm, where N is the number of delivery batches, is presented to find a feasible schedule. A dynamic programming algorithm with O(N ^F /F ^F–2) running time is presented to find an optimal schedule. If F=2 and setup costs are unit, an O(N) time algorithm is derived.     

Efficient algorithms for the matrix cosine and sine

Several improvements are made to an algorithm of Higham and Smith for computing the matrix cosine. The original algorithm scales the matrix by a power of 2 to bring the ∞-norm to 1 or less, evaluates the [8/8] Padé approximant, then uses the double-angle formula cos (2A)=2cos ²A−I to recover the cosine of the original matrix. The first improvement is to phrase truncation error bounds in terms of ‖A²‖^1/2 instead of the (no smaller and potentially much larger quantity) ‖A‖. The second is to choose the degree of the Padé approximant to minimize the computational cost subject to achieving a desired truncation error. A third improvement is to use an absolute, rather than relative, error criterion in the choice of Padé approximant; this allows the use of higher degree approximants without worsening an a priori error bound. Our theory and experiments show that each of these modifications brings a reduction in computational cost. Moreover, because the modifications tend to reduce the number of double-angle steps they usually result in a more accurate computed cosine in floating point arithmetic. We also derive an algorithm for computing both cos (A) and sin (A), by adapting the ideas developed for the cosine and intertwining the cosine and sine double angle recurrences. AMS subject classification 65F30 Numerical Analysis Report 461, Manchester Centre for Computational Mathematics, February 2005. Gareth I. Hargreaves: This work was supported by an Engineering and Physical Sciences Research Council Ph.D. Studentship. Nicholas J. Higham: This work was supported by Engineering and Physical Sciences Research Council grant GR/T08739 and by a Royal Society–Wolfson Research Merit Award.     

Convergence results for a class of spectrally hyperviscous models of 3-D turbulent flow

We consider the spectrally hyperviscous Navier–Stokes equations (SHNSE) which add hyperviscosity to the NSE but only to the higher frequencies past a cutoff wavenumber _m0$m_0$. In Guermond and Prudhomme (2003) [18], subsequence convergence of SHNSE Galerkin solutions to dissipative solutions of the NSE was achieved in a specific spectral-vanishing-viscosity setting. Our goal is to obtain similar results in a more general setting and to obtain convergence to the stronger class of Leray solutions. In particular we obtain subsequence convergence of SHNSE strong solutions to Leray solutions of the NSE by fixing the hyperviscosity coefficient μ$\mu$ while the spectral hyperviscosity cutoff _m0$m_0$ goes to infinity. This formulation presents new technical challenges, and we discuss how its motivation can be derived from computational experiments, e.g. those in Borue and Orszag (1996, 1998)  and . We also obtain weak subsequence convergence to Leray weak solutions under the general assumption that the hyperviscous coefficient μ$\mu$ goes to zero with no constraints imposed on the spectral cutoff. In both of our main results the Aubin Compactness Theorem provides the underlying framework for the convergence to Leray solutions.     

Integrating across Pascal's triangle

Sums across the rows of Pascal's triangle yield n² while certain diagonal sums yield the Fibonacci numbers which are asymptotic to ?n where ? is the golden ratio. Sums across other diagonals yield quantities asymptotic to cn where c depends on the directions of the diagonals. We generalize this to the continuous case. Using the gamma function, we generalize the binomial coefficients to real variables and thus form a generalization of Pascal's triangle. Integration over various families of lines and curves yields quantities asymptotic to cx where c is determined by the family and x is a parameter. Finally, we revisit the discrete case to get results on sums along curves.     

Cyclic networks with general blocking and starvation

We introducegeneral starvation and consider cyclic networks withgeneral blocking and starvation (GBS). The mechanism of general blocking allows the server to process a limited number of jobs when the buffer downstream is full, and that of general starvation allows the server to perform a limited number of services in anticipation of jobs that are yet to arrive. The two main goals of this paper are to investigate how the throughput of cyclic GBS networks is affected by varying (1) the total number of jobsJ, and (2) the buffer allocationk=(k₁..., k_m) subject to a fixed total buffer capacityK=k ₁ +... + k_m. In particular, we obtain sufficient conditions for the throughput to be symmetric inJ and to be maximized whenJ=K/2. We also show that the equal buffer allocation is optimal under the two regimes of light or heavy usage. In order to establish these results, we obtain several intermediate structural properties of the throughput, using duality, reversibility, and concavity, which are of independent interest.Research supported in part by NSF Grant No. ECS-8919818.     

Weighted zeta functions for quotients of regular coverings of graphs

Let G be a connected graph. We reformulate Stark and Terras' Galois Theory for a quotient H of a regular covering K of a graph G by using voltage assignments. As applications, we show that the weighted Bartholdi L-function of H associated to the representation of the covering transformation group of H is equal to that of G associated to its induced representation in the covering transformation group of K. Furthermore, we express the weighted Bartholdi zeta function of H as a product of weighted Bartholdi L-functions of G associated to irreducible representations of the covering transformation group of K. We generalize Stark and Terras' Galois Theory to digraphs, and apply to weighted Bartholdi L-functions of digraphs.     

k-intolerant capacities and Choquet integrals

We define an aggregation function to be (at most) k-intolerant if it is bounded from above by its kth lowest input value. Applying this definition to the discrete Choquet integral and its underlying capacity, we introduce the concept of k-intolerant capacities which, when varying k from 1 to n, cover all the possible capacities on n objects. Just as the concepts of k-additive capacities and p-symmetric capacities have been previously introduced essentially to overcome the problem of computational complexity of capacities, k-intolerant capacities are proposed here for the same purpose but also for dealing with intolerant or tolerant behaviors of aggregation. We also introduce axiomatically indices to appraise the extent to which a given capacity is k-intolerant and we apply them on a particular recruiting problem.     

球上Zygmund 型空间上的加权Cesàro 算子

该文在Cⁿ中单位球上讨论了Zygmund 型空间(小Zygmund 型空间)之间的加权Cesàro 算子T_g 的有界性和紧性特征, 得到了以下的结果: (1) T_g 是Z^p 到Z^q的有界算子或紧算子的充要条件; (2) T_g 是 Z^p₀ 到Z^q₀ 的有界算子或紧算子的充要条件.     

Research announcement on gaierkirfs method for a class of integra equations of the first kind

Let X and Y be locally convex spaces with K a closed convex cone in X Necessary and sufficient conditions are given for the image AK to be closed in Ywhen A:X→Y is a continuous linear map. This result is used to generalize a theorem of Abrams to infinite dimensional spaces and also to give sufficient conditions for the Hurwicz version of the Farkas lemma for locally convex spaces to hold.     

Evaluating the boundary and covering degree of planar Minkowski sums and other geometrical convolutions

Algorithms are developed, based on topological principles, to evaluate the boundary and “internal structure” of the Minkowski sum of two planar curves. A graph isotopic to the envelope curve is constructed by computing its characteristic points. The edges of this graph are in one-to-one correspondence with a set of monotone envelope segments. A simple formula allows a degree   to be assigned to each face defined by the graph, indicating the number of times its points are covered by the Minkowski sum. The boundary can then be identified with the set of edges that separate faces of zero and non-zero degree, and the boundary segments corresponding to these edges can be approximated to any desired geometrical accuracy. For applications that require only the Minkowski sum boundary, the algorithm minimizes geometrical computations on the “internal” envelope edges, that do not contribute to the final boundary. In other applications, this internal structure is of interest, and the algorithm provides comprehensive information on the covering degree for different regions within the Minkowski sum. Extensions of the algorithm to the computation of Minkowski sums in R³${\mathbb{R}}^3$, and other forms of geometrical convolution, are briefly discussed.     

TVaR-based capital allocation for multivariate compound distributions with positive continuous claim amounts

In this paper, we consider a portfolio of n dependent risks X₁,…,X_n and we study the stochastic behavior of the aggregate claim amount S=X₁+?+X_n. Our objective is to determine the amount of economic capital needed for the whole portfolio and to compute the amount of capital to be allocated to each risk X₁,…,X_n. To do so, we use a top-down approach. For (X₁,…,X_n), we consider risk models based on multivariate compound distributions defined with a multivariate counting distribution. We use the TVaR to evaluate the total capital requirement of the portfolio based on the distribution of S, and we use the TVaR-based capital allocation method to quantify the contribution of each risk. To simplify the presentation, the claim amounts are assumed to be continuously distributed. For multivariate compound distributions with continuous claim amounts, we provide general formulas for the cumulative distribution function of S, for the TVaR of S and the contribution to each risk. We obtain closed-form expressions for those quantities for multivariate compound distributions with gamma and mixed Erlang claim amounts. Finally, we treat in detail the multivariate compound Poisson distribution case. Numerical examples are provided in order to examine the impact of the dependence relation on the TVaR of S, the contribution to each risk of the portfolio, and the benefit of the aggregation of several risks.     

The stable ATA-orthogonal s-step Orthomin(k) algorithm with the CADNA library

The major drawback of the s-step iterative methods for nonsymmetric linear systems of equations is that, in the floating-point arithmetic, a quick loss of orthogonality of s-dimensional direction subspaces can occur, and consequently slow convergence and instability in the algorithm may be observed as s gets larger than 5. In [18], Swanson and Chronopoulos have demonstrated that the value of s in the s-step Orthomin(k) algorithm can be increased beyond s=5 by orthogonalizing the s direction vectors in each iteration, and have shown that the A^TA-orthogonal s-step Orthomin(k) is stable for large values of s (up to s=16). The subject of this paper is to show how by using the CADNA library, it is possible to determine a good value of s for A^TA-orthogonal s-step Orthomin(k), and during the run of its code to detect the numerical instabilities and to stop the process correctly, and to restart the A^TA-orthogonal s-step Orthomin(k) in order to improve the computed solution. Numerical examples are used to show the good numerical properties. This revised version was published online in June 2006 with corrections to the Cover Date.     

On error operators related to the arbitrary functions principle

The error on a real quantity Y due to the graduation of the measuring instrument may be asymptotically represented, when the graduation is regular and fines down, by a Dirichlet form on R whose square field operator does not depend on the probability law of Y as soon as this law possesses a continuous density. This feature is related to the “arbitrary functions principle” (Poincaré, Hopf). We give extensions of this property to Rd and to the Wiener space for some approximations of the Brownian motion. This gives new approximations of the Ornstein-Uhlenbeck gradient. These results apply to the discretization of some stochastic differential equations encountered in mechanics.     

The rotor-router model on regular trees

The rotor-router model is a deterministic analogue of random walk. It can be used to define a deterministic growth model analogous to internal DLA. We show that the set of occupied sites for this model on an infinite regular tree is a perfect ball whenever it can be, provided the initial rotor configuration is acyclic (that is, no two neighboring vertices have rotors pointing to one another). This is proved by defining the rotor-router group of a graph, which we show is isomorphic to the sandpile group. We also address the question of recurrence and transience: We give two rotor configurations on the infinite ternary tree, one for which chips exactly alternate escaping to infinity with returning to the origin, and one for which every chip returns to the origin. Further, we characterize the possible “escape sequences” for the ternary tree, that is, binary words a₁…an for which there exists a rotor configuration so that the kth chip escapes to infinity if and only if ak=1.     

Entropy function spaces and interpolation

We associate to every function space, and to every entropy function E, a scale of spaces Λp,q(E) similar to the classical Lorentz spaces Lp,q. Necessary and sufficient conditions for they to be normed spaces are proved, their role in real interpolation theory is analyzed, and a number of applications to functional and interpolation properties of several variants of Lorentz spaces and entropy spaces are given.     

Intertwining wavelets or multiresolution analysis on graphs through random forests

We propose a new method for performing multiscale analysis of functions defined on the vertices of a finite connected weighted graph. Our approach relies on a random spanning forest to downsample the set of vertices, and on approximate solutions of Markov intertwining relation to provide a subgraph structure and a filter bank leading to a wavelet basis of the set of functions. Our construction involves two parameters q and $q^{\prime }$. The first one controls the mean number of kept vertices in the downsampling, while the second one is a tuning parameter between space localization and frequency localization. We provide an explicit reconstruction formula, bounds on the reconstruction operator norm and on the error in the intertwining relation, and a Jackson-like inequality. These bounds lead to recommend a way to choose the parameters q and $q^{\prime }$. We illustrate the method by numerical experiments.