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.     

Safe solutions of a nonlinear car-following equation

A leader-follower pair of cars whose motion is subject to a non-linear delay differential equation are travelling with the same constant velocity u_I when the leader begins to change his velocity in a smooth way to the non-negative velocity u_F < u_I. Conditions are found for the response of the follower to be a safe one according to certain natural safety criteria.     

The second twisted Betti number and the convergence of collapsing Riemannian manifolds

Let M _i X denote a sequence of n-manifolds converging to a compact metric space, X, in the Gromov-Hausdorff topology such that the sectional curvature is bounded in absolute value and dim(X)<n. We prove the following stability result: If the fundamental groups of M _i are torsion groups of uniformly bounded exponents and the second twisted Betti numbers of M _i vanish, then there is a manifold, M, and a sequence of diffeomorphisms from M to a subsequence of {M _i } such that the distance functions of the pullback metrics converge to a pseudo-metric in C ⁰-norm. Furthermore, M admits a foliation with leaves diffeomorphic to flat manifolds (not necessarily compact) such that a vector is tangent to a leaf if and only if its norm converges to zero with respect to the pullback metrics. These results lead to a few interesting applications. Oblatum 17-I-2002 & 27-II-2002?Published online: 29 April 2002     

Conjugate function theory in weak1 Dirichlet algebras

The fundamental theorems on conjugate functions are shown to be valid for weak¹ Dirichlet algebras. In particular the conjugation operator is shown to be a continuous map of L^p to L^p for 1 < p < ∞, to be a continuous map of L¹ to L^p, 0 < p < 1, and to map functions in L^∞ to exponentially integrable functions. These results allow a number of results for Dirichlet algebras to be extended to weak¹ Dirichlet algebras.     

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.     

Poisson convergence in the restricted k‐partitioning problem

The randomized k‐number partitioning problem is the task to distribute N i.i.d. random variables into k groups in such a way that the sums of the variables in each group are as similar as possible. The restricted k‐partitioning problem refers to the case where the number of elements in each group is fixed to N/k. In the case k = 2 it has been shown that the properly rescaled differences of the two sums in the close to optimal partitions converge to a Poisson point process, as if they were independent random variables. We generalize this result to the case k > 2 in the restricted problem and show that the vector of differences between the k sums converges to a k ‐ 1‐dimensional Poisson point process. © 2006 Wiley Periodicals, Inc. Random Struct. Alg., 2007     

Optimal Control of the Obstacle for an Elliptic Variational Inequality

An optimal control problem for an elliptic obstacle variational inequality is considered. The obstacle is taken to be the control and the solution to the obstacle problem is taken to be the state. The goal is to find the optimal obstacle from H ¹ ₀ (Ω) so that the state is close to the desired profile while the H ¹ (Ω) norm of the obstacle is not too large. Existence, uniqueness, and regularity as well as some characterizations of the optimal pairs are established. Accepted 11 September 1996     

From Endomorphisms to Automorphisms and Back: Dilations and Full Corners

When S is a discrete subsemigroup of a discrete group G suchthat G = S^–1S, it is possible to extend circle-valuedmultipliers from S to G, to dilate (projective) isometric representationsof S to (projective) unitary representations of G, and to dilate/extendactions of S by injective endomorphisms of a C*-algebra to actionsof G by automorphisms of a larger C*-algebra. These dilationsare unique provided they satisfy a minimality condition. The(twisted) semigroup crossed product corresponding to an actionof S is isomorphic to a full corner in the (twisted) crossedproduct by the dilated action of G. This shows that crossedproducts by semigroup actions are Morita equivalent to crossedproducts by group actions, making powerful tools available tostudy their ideal structure and representation theory. The dilationof the system giving the Bost–Connes Hecke C*-algebrafrom number theory is constructed explicitly as an application:it is the crossed product C₀(A_f)Q*₊, corresponding to the multiplicativeaction of the positive rationals on the additive group A_f offinite adeles.     

On the singularities of foliations and of vector bundle maps

LetF be a (smooth) Γ _q ^∞ -stucture (often called a codimension-q Haefliger structure) on a compact manifoldX ⁿ . Cohomological invariants associated to the singularities ofF are defined whose vanishing is shown to be a necessary condition for deformingF to a codimension-q foliation onX ⁿ . An analagous approach to vector bundle maps is then utilized to prove a general theorem concerning the possibility of embedding a vector bundle in the tangent bundle ofX ⁿ , and applications to the planefield problem are given. In the final section geometric realizations of the singularity classes associated toF are constructed.     

On the asymptotics with respect to a parameter of solutions of differential systems with coefficients in the class <Emphasis Type="Italic">L</Emphasis><Subscript><Emphasis Type="Italic">q</Emphasis></Subscript>

We consider a system of first-order ordinary linear differential equations with coefficients depending on an arbitrary parameter λ. For large λ, if the coefficients are smooth with respect to x, then there are known classical exponentially asymptotic (with respect to λ) formulas for the solution of the system. We generalize such formulas to the case in which the coefficients belong to the class L _q , q > 1. We use a new method for the reduction of problems to an integral system of special form.     

Application of fast spherical Fourier transform to density estimation

This paper is on density estimation on the 2-sphere, S², using the orthogonal series estimator corresponding to spherical harmonics. In the standard approach of truncating the Fourier series of the empirical density, the Fourier transform is replaced with a version of the discrete fast spherical Fourier transform, as developed by Driscoll and Healy. The fast transform only applies to quantitative data on a regular grid. We will apply a kernel operator to the empirical density, to produce a function whose values at the vertices of such a grid will be the basis for the density estimation. The proposed estimation procedure also contains a deconvolution step, in order to reduce the bias introduced by the initial kernel operator. The main issue is to find necessary conditions on the involved discretization and the bandwidth of the kernel operator, to preserve the rate of convergence that can be achieved by the usual computationally intensive Fourier transform. Density estimation is considered in L²(S²) and more generally in Sobolev spaces H_v(S²), any v?0, with the regularity assumption that the probability density to be estimated belongs to H_s(S²) for some s>v. The proposed technique to estimate the Fourier transform of an unknown density keeps computing cost down to order O(n), where n denotes the sample size.     

On eigenvalue pinching in positive Ricci curvature

We shall show that for manifolds with Ric≥n−1 the radius is close to π iff the (n+1)st eigenvalue is close to n. This extends results of Cheng and Croke which show that the diameter is close to π iff the first eigenvalue is close to n. We shall also give a new proof of an important theorem of Colding to the effect that if the radius is close to π, then the volume is close to that of the sphere and the manifold is Gromov-Hausdorff close to the sphere. From work of Cheeger and Colding these conditions imply that the manifold is diffeomorphic to a sphere. Oblatum 29-V-1998 & 4-II-1999 / Published online: 21 May 1999     

Nahm's equations, configuration spaces and flag manifolds

We give a positive answer to the Berry-Robbins problem for any compact Lie group G, i.e. we show the existence of a smooth W-equivariant map from the space of regular triples in a Cartan subalgebra to the flag manifold G/T . This map is constructed via solutions to Nahm's equations and it is compatible with the S O(3) action, where S O(3) acts on G/T via a regular homomorphism from S U(2) to G. We then generalize this picture to include an arbitrary homomorphism from S U(2) to G. This leads to an interesting geometrical picture which appears to be related to the Springer representation of the Weyl group and the work of Kazhdan and Lusztig on representations of Hecke algebras. Received: 8 February 2002     

Compression and denoising using <Emphasis Type="Italic">l</Emphasis><Subscript>0</Subscript>-norm

In this paper, we deal with l ₀-norm data fitting and total variation regularization for image compression and denoising. The l ₀-norm data fitting is used for measuring the number of non-zero wavelet coefficients to be employed to represent an image. The regularization term given by the total variation is to recover image edges. Due to intensive numerical computation of using l ₀-norm, it is usually approximated by other functions such as the l ₁-norm in many image processing applications. The main goal of this paper is to develop a fast and effective algorithm to solve the l ₀-norm data fitting and total variation minimization problem. Our idea is to apply an alternating minimization technique to solve this problem, and employ a graph-cuts algorithm to solve the subproblem related to the total variation minimization. Numerical examples in image compression and denoising are given to demonstrate the effectiveness of the proposed algorithm.     

Pricing and volume discounting for a dominant retailer with uncertain manufacturing cost information

A product costs the manufacturer c/unit to produce; the retailer sells it at p/unit to the consumers. The retail-market demand volume V varies with p according to a given demand curve D_p. How would or should the “players” (i.e., the manufacturer and the retailer) set their prices? In contrast to many studies that assume a dominant manufacturer implementing the “manufacturer-Stackelberg” (“[mS]”) game, this paper examines how a dominant retailer should operate when his knowledge of c is imperfect. We first derive optimal decisions (some of them counter-intuitive) for the dominant retailer when he is restricted to choosing between [rS] (retailer-Stackelberg) and [mS]. Second, we propose a “reverse quantity discount” scheme that the dominant retailer (i.e., the downstream player) can offer to the manufacturer (note that the standard discount scheme is offered by the upstream player). We show that this discounting scheme is quite effective compared to the considerably more complicated though nevertheless theoretically optimal “menu of contracts.” We also reveal a largely overlooked function of discounting; i.e., discounting enables an “ignorant” but dominant player to usurp the earnings attributable to the knowledge of the dominated player. Finally, we also show that discounting works well when the demand curve is linear, but becomes ineffective when the demand curve is iso-elastic – a result echoing the conclusions of some earlier related works.     

Energetic reasoning and bin-packing problem, for bounding a parallel machine scheduling problem

This paper deals with an extension of energetic reasoning, using some efficient lower bounds of the bin-packing problem, to get tight lower bounds for the P|r _i , q _i |C _max. The link between P||C _max and bin-packing problem is well-known. Our purpose is to extend the use of efficient lower bounds of the bin-packing problem to P|r _i , q _i |C _max. We focus on some time-intervals, to compute the mandatory parts of activities within this time-interval and then to deduce an associated bin-packing instance. Thus, lower bounds of the bin-packing problem are used to get new satisfiability tests for the parallel machine problem. We also propose to extend the classical time-bound adjustments of release dates and deadlines to efficiently use bin-packing lower bounds. Experimental results that prove the efficiency of our approach on several kind of instances are reported.     

Translated Poisson Approximation for Markov Chains

The paper is concerned with approximating the distribution of a sum W of integer valued random variables Y _i , 1 ≤ i ≤ n, whose distributions depend on the state of an underlying Markov chain X. The approximation is in terms of a translated Poisson distribution, with mean and variance chosen to be close to those of W, and the error is measured with respect to the total variation norm. Error bounds comparable to those found for normal approximation with respect to the weaker Kolmogorov distance are established, provided that the distribution of the sum of the Y _i ’s between the successive visits of X to a reference state is aperiodic. Without this assumption, approximation in total variation cannot be expected to be good.