On-Line Scheduling of Unit Time Jobs with Rejection on Uniform Machines

The authors consider the problem of on-line scheduling of unit execution time jobs on uniform machines with rejection penalty. The jobs arrive one by one and can be either accepted and scheduled, or be rejected. The objective is to minimize the total completion time of the accepted jobs and the total penalty of the rejection jobs. The authors propose an on-line algorithm and prove that the competitive ratio is 1/2 （2 W √3） ≈ 1.86602.     

SCHEDULING WITH REJECTION AND NON-IDENTICAL JOB ARRIVALS

In this paper, we address the scheduling problem with rejection and non-identical job arrivals, in which we may choose not to process certain jobs and each rejected job incurs a penalty, Our goal is to minimize the sum of the total penalties of the rejected jobs and the maximum completion time of the processed ones, For the off-line variant, we prove its NP-hardness and present a PTAS, and for the on-line special case with two job arrivals, we design a best possible algorithm with competitive ratio （√5＋1/2） .     

An on-line scheduling problem of parallel machines with common maintenance time

In this paper, the authors consider an on-line scheduling problem of m (m ≥ 3) identical machines with common maintenance time interval and nonresumable availability. For the case that the length of maintenance time interval is larger than the largest processing time of jobs, the authors prove that any on-line algorithm has not a constant competitive ratio. For the case that the length of maintenance time interval is less than or equal to the largest processing time of jobs, the authors prove a lower bound of 3 on the competitive ratio. The authors give an on-line algorithm with competitive ratio $4 - \tfrac{1} {m} $ . In particular, for the case of m = 3, the authors prove the competitive ratio of the on-line algorithm is $\tfrac{{10}} {3} $ .     

SEMI ON-LINE SCHEDULING PROBLEM FOR MAXIMIZING THE MINIMUM MACHINE COMPLETION TIME ON TWO UNIFORM MACHINES

Ia this paper, we consider a semi on-line version on two uniform machines Mi, i = 1, 2, where the processing time of the largest job is known in advance. A speed si（s1 = 1, 1 ≤s2 = s） is associated with machine Mi. Our goal is to maximize the Cmin. We give a Cmin 2 algorithm and prove its competitive ratio is at most 2s＋1/s＋1 We also claim the Cmin 2 algorithm is tight and the gap between the competitive ratio of Cmin2 algorithm and the optimal value is not greater than 0.555. It is obvious that our result coincides with that given by He for s =1.     

Asymptotic Normality of Maximum Quasi-Likelihood Estimators in Generalized Linear Models with Fixed Design*

In generalized linear models with fixed design, under the assumption λ↑_n→∞ and other regularity conditions, the asymptotic normality of maximum quasi-likelihood estimator ^↑βn, which is the root of the quasi-likelihood equation with natural link function ∑i=1^n Xi（yi -μ（Xi′β）） = 0, is obtained, where λ↑_n denotes the minimum eigenvalue of ∑i=1^nXiXi′, Xi are bounded p × q regressors, and yi are q × 1 responses.     

ON THE MEROMORPHIC SOLUTIONS OF LINEAR DIFFERENTIAL EQUATIONS

In this paper, we investigate the growth of meromorphic solutions of higher order linear differential equation f^（k） ＋Ak-1 （z）e^Pk-1^（z） f^（k-1） ＋…＋A1 （z）e^P1（z） f′ ＋Ao（z）e^Po（z） f = 0 （k ≤ 2）, where Pj（z） （j = 0, 1,..., k - 1） are nonconstant polynomials such that deg Pj = n （j = 0, 1,..., k - 1） and Aj（z）（≠ 0） （j = 0, 1,..., k - 1） are meromorphic functions with order p（Aj） 〈 n （j = 0, 1,..., k - 1）.     

TWO-WEIGHT NORM INEQUALITY FOR IMAGINARY POWERS OF A LAPLACE OPERATOR

We study two-weight norm inequality for imaginary powers of a Laplace operator in R^n, n ≥ 1, especially from weighted Lebesgue space Lv^p（R^n） to weighted Lebesgue space Lμ^p（R^n）, where 1 〈 p 〈 ∞. We prove that the two-weighted norm inequality holds whenever for some t 〉 1, （μ^t, v^t） ∈ Ap, or if （μ, v） ∈Ap, where μ and v^-1/（p-1） satisfy the growth condition and reverse doubling property.     

ON THE ALMOST SURELY ASYMPTOTIC BOUNDS OF A CLASS OF ORNSTEIN-UHLENBECK PROCESSES IN INFINITE DIMENSIONS*

Given a real-valued separable M-type 2 Banach space X with the p-th power of the norm of C2-class, the almost sure asymptotic upper bounds of the solutions of the Ornstein-Uhlenbeck Processes described by the following equations {dz（t）=A（t,z（t））dt＋σ（t,z（t））dW（t）,z（0）=z0∈X,are investigated. This study generalizes the corresponding well-known finite dimensional results of Lapeyre （1989） and Mao （1992）.     

FORCED OSCILLATIONS OF A CLASS OF NONLINEAR DISPERSIVE WAVE EQUATIONS AND THEIR STABILITY

It has been observed in laboratory experiments that when nonlinear dispersive waves are forced periodically from one end of undisturbed stretch of the medium of propagation, the signal eventually becomes temporally periodic at each spatial point. The observation has been confirmed mathematically in the context of the damped Korteweg-de Vries （KdV） equation and the damped Benjamin-Bona-Mahony （BBM） equation. In this paper we intend to show the same results hold for the pure KdV equation （without the damping terms） posed on a finite domain. Consideration is given to the initial-boundary-value problem {ut＋ux＋uux＋uxxx=0, u（x,0）=φ（x）, 0〈x〈1, t〉0,u（0,t）=h（t）, u（1,t） = 0, ux（1,t） = 0, t〉0.It is shown that if the boundary forcing h is periodic with small ampitude, then the small amplitude solution u of （＊） becomes eventually time-periodic. Viewing （＊） （without the initial condition） as an infinite-dimensional dynamical system in the Hilbert space L^2（0, 1）, we also demonstrate that for a given periodic boundary forcing with small amplitude, the system （＊） admits a （locally） unique limit cycle, or forced oscillation, which is locally exponentially stable. A list of open problems are included for the interested readers to conduct further investigations.     

On-Line Scheduling on Parallel Machines to Minimize the Makespan

This paper considers two parallel machine scheduling problems,where the objectives of both problems are to minimize the makespan,and the jobs arrive over time,on two uniform machines with speeds 1 and s(s≥1),and on m identical machines,respectively.For the first problem,the authors show that the on-line LPT algorithm has a competitive ratio of(1 +5~(1/2))/2≈1.6180 and the bound is tight.Furthermore,the authors prove that the on-line LPT algorithm has the best possible competitive ratio if s≥1.8020.For the second problem,the authors present a lower bound of(15-(17)~(1/2))/8≈1.3596 on the competitive ratio of any deterministic on-line algorithm.This improves a previous result of 1.3473.     

A NEW FAMILY OF TRIVALENT CAYLEY NETWORKS ON WREATH PRODUCT Zm ～ Sn

We propose a new family of interconnection networks （WGn^m） with regular degree three. When the generator set is chosen properly, they are isomorphic to Cayley graphs on the wreath product Zm ～ Sn. In the case of m ≥ 3 and n ≥3, we investigate their different algebraic properties and give a routing algorithm with the diameter upper bounded by [m/2]（3n^2- 8n ＋ 4） - 2n ＋ 1. The connectivity and the optimal fault tolerance of the proposed networks are also derived. In conclusion, we present comparisons of some familiar networks with constant degree 3.     

DETERMINING WHETHER A MULTIVARIATE HYPEREXPONENTIAL FUNCTION IS ALGEBRAIC

Let F=C（x1,x2,…,xe,xe＋1,…,xm）, where x1, x2,… , xe are differential variables, and xe＋1,…,xm are shift variables. We show that a hyperexponential function, which is algebraic over F,is of form g（x1, x2, …,xm）q（x1,x2,…,xe）^1/lwe＋1^xe＋1…wm^xm, where g∈ F, q ∈ C（x1,x2,…,xe）,t∈Z^＋ and we＋1,…,wm are roots of unity. Furthermore,we present an algorithm for determining whether a hyperexponential function is algebraic over F.     

Improved Algorithm for Minimum Data Aggregation Time Problem in Wireless Sensor Networks

Wireless sensor networks promise a new paradigm for gathering data via collaboration among sensors spreading over a large geometrical region. Many applications impose delay requirements for data gathering and ask for time-efficient schedules for aggregating sensed data and sending to the data sink. In this paper, the authors study the minimum data aggregation time problem under collision-free transmission model. In each time round, data sent by a sensor reaches all sensors within its transmission range, but a sensor can receive data only when it is the only data that reaches the sensor. The goal is to find the method that schedules data transmission and aggregation at sensors so that the time for all requested data to be sent to the data sink is minimal. The authors propose a 7△/log2｜s｜＋c, new approximation algorithm for this NP-hard problem with guaranteed performance ratio which significantly reduces the current best ratio of △- 1, where S is the set of sensors containing source data, A is the maximal number of sensors within the transmission range of any sensor, and e is a constant. The authors also conduct extensive simulation, the obtained results justify the improvement of proposed algorithm over the existing one.     

On the single server retrial queue with priority subscribers and server breakdowns

The author concerned the reliability evaluation as well as queueing analysis of M1, M2/G1, G2/1 retrial queues with two different types of primary customers arriving according to independent Poisson flows. In the case of blocking, the first type of customers can be queued whereas the second type of customers must leave the service area but return after some random period of time to try their luck again. The author assumes that the server is unreliable and it has a service-type dependent, exponentially distributed life time as well as a service-type dependent, generally distributed repair time. The necessary and sufficient condition for the system to be stable is investigated. Using a supplementary variable method, the author obtains a steady-state solution for queueing measures, and the transient as well as the steady-state solutions for reliability measures of interest.     

Construction of one-Lee weight and two-Lee weight codes over F<Subscript><Emphasis Type="Italic">p</Emphasis></Subscript> + <Emphasis Type="Italic">v</Emphasis>F<Subscript><Emphasis Type="Italic">p</Emphasis></Subscript>

This paper is devoted to the construction of one-Lee weight codes and two-Lee weight codes over F _p + vF _p (v ² = v) with type \({p^{2{k_1}}}{p^{{k_2}}}{p^{{k_3}}}\) based on two different distance-preserving Gray maps from ((F _p + vF _p ) ⁿ , Lee weight) to (F _p ²ⁿ , Hamming weight), where p is a prime. Moreover, the authors prove that the obtained two-Lee weight codes are projective only when p = 2.     

PRE-IMAGE ENTROPY OF NONAUTONOMOUS DYNAMICAL SYSTEMS*

The authors define and study topological pre-image entropy for the non-autonomous discrete dynamical systems given by a sequence {fi}i=1^∞ of continuous self-maps of a compact topological space. The basic properties and the invariant with respect to equiconjugacy of pre-image entropy for the non-autonomous discrete dynamical systems are obtained.     

Testing <Emphasis Type="Italic">k</Emphasis>-edge-connectivity of digraphs

This paper presents an algorithm that tests whether a given degree-bounded digraph is k-edge-connected or ɛ-far from k-edge-connectivity. This is the first testing algorithm for k-edgeconnectivity of digraphs whose running time is independent of the number of vertices and edges. A digraph of n vertices with degree bound d is ɛ-far from k-edge-connectivity if at least ɛdn edges have to be added or deleted to make the digraph k-edge-connected, preserving the degree bound. Given a constant error parameter ɛ and a degree bound d, our algorithm always accepts all k-edge-connected digraphs and rejects all digraphs that is ɛ-far from k-edge-connectivity with probability at least 2/3. It runs in $ O\left( {d\left( {\frac{c} {{\varepsilon d}}} \right)^k log\frac{1} {{\varepsilon d}}O} \right) $ O\left( {d\left( {\frac{c} {{\varepsilon d}}} \right)^k log\frac{1} {{\varepsilon d}}O} \right) (c > 1 is a constant) time when input digraphs are restricted to be (k-1)-edge connected and runs in $ O\left( {d\left( {\frac{{ck}} {{\varepsilon d}}} \right)^k log\frac{k} {{\varepsilon d}}O} \right) $ O\left( {d\left( {\frac{{ck}} {{\varepsilon d}}} \right)^k log\frac{k} {{\varepsilon d}}O} \right) (c > 1 is a constant) time for general digraphs.     

The limit theorem for dependent random variables with applications to autoregression models

This paper studies the autoregression models of order one, in a general time series setting that allows for weakly dependent innovations. Let {X _t } be a linear process defined by X _t = Σ _k=0^∞ψ _k ɛ _t−k , where {ψ _k , k ≥ 0} is a sequence of real numbers and {ɛ _k , k = 0, ±1, ±2, …} is a sequence of random variables. Two results are proved in this paper. In the first result, assuming that {ɛ _k , k ≥ 1} is a sequence of asymptotically linear negative quadrant dependent (ALNQD) random variables, the authors find the limiting distributions of the least squares estimator and the associated regression t statistic. It is interesting that the limiting distributions are similar to the one found in earlier work under the assumption of i.i.d. innovations. In the second result the authors prove that the least squares estimator is not a strong consistency estimator of the autoregressive parameter α when {ɛ _k , k ≥ 1} is a sequence of negatively associated (NA) random variables, and ψ ₀ = 1, ψ _k = 0, k ≥ 1.     

Some Results on Generalized Difference Sets

Sequences with ideal correlation functions have important applications in communications such as CDMA, FDMA, etc. It has been shown that difference sets can be used to construct such sequences. The author extends Pott and Bradley＇s method to a much broader case by proposing the concept of generalized difference sets. Some necessary conditions for the existence of generalized difference sets are established by means of some Diophantine equations. The author also provides an algorithm to determine the existence of generalized difference sets in the cyclic group Zv. Some examples are presented to illustrate that our method works.