Loss probability in an overloaded discrete-time GI/G/1/K system with very large K

We present a simple semi-explicit formula for estimating the loss probability in a discrete-time GI/G/1/K system (with large K) which is operating under an overload condition. The method relaxes the lower boundary and then studies the upper boundary only. The idea is extended to the GI^X/G/1/K system.     

Sojourn times in (discrete) time shared systems and their continuous time limits

We study the mean sojourn times in two M/G/1 weighted round-robin systems: the weight of a customer at any given point in time in the first system is a function of its age (imparted service), while in the second system the weight is a function of the customer’s remaining processing time (RPT). We provide a sufficient condition under which the sojourn time of a customer with large service requirement (say, x) and that arrives in the steady state is close to that of a customer which starts a busy period and has the same service requirement. A sufficient condition is then provided for continuity of the performance metric (the mean sojourn time) as the quanta size in the discrete time system converges to 0. We then consider a multi-class system and provide relative ordering of the mean sojourn times among the various classes.     

Approximating the Mean Waiting Time in the <Emphasis Type="Italic">GI/G/s</Emphasis> Queue

We provide two distribution-dependent approximations for the mean waiting time in a GI/G/s queue. Both approximations are weighted combinations of the exact mean waiting times for the GI/M/s and M/D/s queues each of which has the same mean service time and traffic intensity as in the approximating GI/G/s queue. The weights in the approximations are expressed by the service-time c.d.f. and the first two moments of interarrival and service times. To examine the performance of our approximations, they are numerically compared with exact solutions and previous two-moment approximations for various cases. Extensive numerical comparisons indicate that the relative percentage errors of the approximations are of the order of 5% in moderate traffic and 1% in heavy traffic, except for extreme cases.     

On the Queue Length Distribution for the GI/G/1/K/VM Queue

Abstract

We present a transform-free distribution of the steady-state queue length for the GI/G/1/K queueing system with multiple vacations under exhaustive FIFO service discipline. The method we use is a modified supplementary variable technique and the result we obtain is expressed in terms of conditional expectations of the remaining service time, the remaining interarrival time, and the remaining vacation, conditional on the queue length at the embedded points. The case K → ∞ is also considered.     

A unified algorithm for computing the stationary queue length distributions inM(k)/G/1/N and GI/M(k)/1/N queues

An iterative algorithm is developed for computing numerically the stationary queue length distributions in M/G/1/N queues with arbitrary state-dependent arrivals, or simply M(k)/G/1/N queues. The only input requirement is the Laplace-Stieltjes transform of the service time distribution.In addition, the algorithm can also be used to obtain the stationary queue length distributions in GI/M/1/N queues with state-dependent services, orGI/M(k)/1/N, after establishing a relationship between the stationary queue length distributions inGI/M(k)/1/N and M(k)/G/1/N+1 queues.Finally, we elaborate on some of the well studied special cases, such asM/G/1/N queues,M/G/1/N queues with distinct arrival rates (which includes the machine interference problems), andGI/M/C/N queues. The discussions lead to a simplified algorithm for each of the three cases.     

QMC Rules of Arbitrary High Order: Reproducing Kernel Hilbert Space Approach

In this paper we consider numerical integration of smooth functions lying in a particular reproducing kernel Hilbert space. We show that the worst-case error of numerical integration in this space converges at the optimal rate, up to some power of a log?N factor. A similar result is shown for the mean square worst-case error, where the bound for the latter is always better than the bound for the square worst-case error. Finally, bounds for integration errors of functions lying in the reproducing kernel Hilbert space are given. The paper concludes by illustrating the theory with numerical results.     

Approximate minimum-cost multicommodity flows in\tilde O(ɛ −2 KNM) timetime

We show that an ε-approximate solution of the cost-constrainedK-commodity flow problem on anN-nodeM-arc network,G can be computed by sequentially solving O(K(? ^?2+logGK) logGM log (G? ^?1 GK)) single-commodity minimum-cost flow problems on the same network. In particular, an approximate minimum-cost multicommodity flow can be computed in $\tilde O$ (G? ^?2 GKNM) running time, where the notation Õ(·) means “up to logarithmic factors”. This result improves the time bound mentioned by Grigoriadis and Khachiyan [4] by a factor ofM/N and that developed more recently by Karger and Plotkin [8] by a factor of? ^?1. We also provide a simple $\tilde O$ (NM)-time algorithm for single-commodity budget-constrained minimum-cost flows which is $\tilde O$ (? ^?3) times faster than the algorithm developed in the latter paper.     

On the Hilbert scheme of the moduli space of vector bundles over an algebraic curve

Let M(n, ξ) be the moduli space of stable vector bundles of rank n ≥ 3 and fixed determinant ξ over a complex smooth projective algebraic curve X of genus g ≥ 4. We use the gonality of the curve and r-Hecke morphisms to describe a smooth open set of an irreducible component of the Hilbert scheme of M(n, ξ), and to compute its dimension. We prove similar results for the scheme of morphisms ${M or_P (\mathbb{G}, M(n, \xi))}$ and the moduli space of stable bundles over ${X \times \mathbb{G}}$ , where ${\mathbb{G}}$ is the Grassmannian ${\mathbb{G}(n - r, \mathbb{C}^n)}$ . Moreover, we give sufficient conditions for ${M or_{2ns}(\mathbb{P}^1, M(n, \xi))}$ to be non-empty, when s ≥ 1.     

Logarithmically completely monotonic functions relating to the gamma function

In this paper, the logarithmically complete monotonicity of the function exΓ(x+β)/xx+β−α in (0,∞) for α∈R and β?0 is considered and the corresponding result by G.D. Anderson, R.W. Barnard, K.C. Richards, M.K. Vamanamurthy and M. Vuorinen is generalized. As applications of these results, some inequalities between identric mean and ratio of two gamma functions by J.D. Ke?ki? and P.M. Vasi? are extended.     

K?hler–Einstein metrics on strictly pseudoconvex domains

Extending the results of Cheng and Yau it is shown that a strictly pseudoconvex domain ${M\subset X}$ in a complex manifold carries a complete K?hler–Einstein metric if and only if its canonical bundle is positive, i.e. admits an Hermitian connection with positive curvature. We consider the restricted case in which the CR structure on ${\partial M}$ is normal. In this case M must be a domain in a resolution of the Sasaki cone over ${\partial M}$ . We give a condition on a normal CR manifold which it cannot satisfy if it is a CR infinity of a K?hler–Einstein manifold. We are able to mostly determine those normal CR three-manifolds which can be CR infinities. We give many examples of K?hler–Einstein strictly pseudoconvex manifolds on bundles and resolutions. In particular, the tubular neighborhood of the zero section of every negative holomorphic vector bundle on a compact complex manifold whose total space satisfies c ₁?<?0 admits a complete K?hler–Einstein metric.     

An M/G/1 retrial G-queue with preemptive resume priority and collisions subject to the server breakdowns and delayed repairs

We consider an M/G/1 retrial G-queue with preemptive resume priority and collisions under linear retrial policy subject to the server breakdowns and delayed repairs. A breakdown at the busy server is represented by the arrival of a negative customer which causes the customer being in service to be lost. The stability condition of the system is derived. Using generating function technique, the steady-state distributions of the server state and the number of customers in the orbit are obtained along with some interesting and important performance measures. The stochastic decomposition property is investigated. Further, some special cases of interest are discussed. Finally, numerical illustrations are provided.     

Fluid queue driven by aGI/GI/1 queue

Consider a model consisting of two phases: the GI/GI/1 queue and a buffer which is fed by a fluid arriving from a single-server queue. The fluid output from the GI/GI/1 queue is of the on/off type with on- and off-periods distributed as successive busy and idle periods in the GI/GI/1 queue. The fluid pours out of the buffer at a constant rate. The steady-state performance of this model is studied. We derive the Laplace-Stieltjes transform of the stationary distribution function of the buffer content in the case of the M/GI/1 queue in the first phase. It is shown that this distribution depends on the form of the service-time distribution. Therefore, the replacement of an M/GI/1 queue by an M/M/1 queue is not correct, in general. Continuity estimates are derived in the cast where the buffer is fed from the GI/GI/1 queue. Proceedings of the Seminar on Stability Problems for Stochastic Models, Moscow Russia, 1996, Part II.     

Some thoughts on an O(N3)-algorithm for the optimal control of arrivals in a GI/M/1/N queue

A formerly presented O(N³)-algorithm for the optimal control of arrivals in a GI/M/1/N queue is extended for solving the problems with the average reward criterion and with a general action space.     

A Higgs bundle on a Hermitian symmetric space

Let \(M := \Gamma\backslash G/K\) be the quotient of an irreducible Hermitian symmetric space G/K by a torsionfree cocompact lattice \(\Gamma\subset G\) . There is a natural flat principal G-bundle over the compact Kähler manifold M which is constructed from the principal Γ-bundle over M defined by the quotient map \(G/K\longrightarrow M\) . We construct the principal G-Higgs bundle over M corresponding to this flat G-bundle. This principal G-Higgs bundle is rigid if \({\rm dim}_\mathbb{C} M\,\geq\,2\) .     

Asymptotic behavior of the loss probability for an M/G/1/N queue with vacations

In this paper, asymptotic properties of the loss probability are considered for an M/G/1/N queue with server vacations and exhaustive service discipline, denoted by an M/G/1/N-(V, E)-queue. Exact asymptotic rates of the loss probability are obtained for the cases in which the traffic intensity is smaller than, equal to and greater than one, respectively. When the vacation time is zero, the model considered degenerates to the standard M/G/1/N queue. For this standard queueing model, our analysis provides new or extended asymptotic results for the loss probability. In terms of the duality relationship between the M/G/1/N and GI/M/1/N queues, we also provide asymptotic properties for the standard GI/M/1/N model.     

Flat nearly Kähler manifolds

We classify flat strict nearly Kähler manifolds with (necessarily) indefinite metric. Any such manifold is locally the product of a flat pseudo-Kähler factor of maximal dimension and a strict flat nearly Kähler manifold of split signature (2m, 2m) with m ≥ 3. Moreover, the geometry of the second factor is encoded in a complex three-form $\zeta \in \Lambda^3 (\mathbb{C}^m)^*We classify flat strict nearly K?hler manifolds with (necessarily) indefinite metric. Any such manifold is locally the product of a flat pseudo-K?hler factor of maximal dimension and a strict flat nearly K?hler manifold of split signature (2m, 2m) with m ≥ 3. Moreover, the geometry of the second factor is encoded in a complex three-form . The first nontrivial example occurs in dimension 4m = 12.      

Congruences for 9-regular partitions modulo 3

It is proved that the number of 9-regular partitions of n is divisible by 3 when n is congruent to 3 mod 4, and by 6 when n is congruent to 13 mod 16. An infinite family of congruences mod 3 holds in other progressions modulo powers of 4 and 5. A collection of conjectures includes two congruences modulo higher powers of 2 and a large family of “congruences with exceptions” for these and other regular partitions mod 3.     

Existence of GBRDs with block size 4 and BRDs with block size 5

Chaudhry et al. (J Stat Plann Inference 106:303–327, 2002) have examined the existence of BRD(v, 5, λ)s for \({\lambda \in \{4, 10, 20\}}\). In addition, Ge et al. (J Combin Math Combin Comput 46:3–45, 2003) have investigated the existence of \({{\rm GBRD}(v,4,\lambda; \mathbb{G}){\rm s}}\) when \({\mathbb{G}}\) is a direct product of cyclic groups of prime orders. For the first problem, necessary existence conditions are (i) v ≥ 5, (ii) λ(v ? 1) ≡ 0 (mod4), (iii) λ v(v ? 1) ≡ 0 (mod 40), (iv) λ ≡ 0 (mod 2). We show these are sufficient, except for \({v=5, \lambda \in \{4,10\}}\). For the second problem, we improve the known existence results. Five necessary existence conditions are (i) v ≥ 4, (ii) \({\lambda \equiv 0\;({\rm mod}\,|\mathbb{G}|)}\), (iii) λ(v ? 1) ≡ 0 (mod 3), (iv) λ v(v ? 1) ≡ 0 (mod 4), (v) if v = 4 and \({|\mathbb{G}| \equiv 2\;({\rm mod}\,4)}\) then λ ≡ 0 (mod 4). We show these conditions are sufficient, except for \({\lambda = |\mathbb{G}|, (v,|\mathbb{G}|) \in \{(4,3), (10,2), (5,6), (7,4)\}}\) and possibly for \({\lambda = |\mathbb{G}|, (v,|\mathbb{G}|) \in \{(10,2h), (5,6h), (7,4h)\}}\) with h ≡ 1 or 5 (mod 6), h > 1.     

A single interval based classifier

In many applications, it is desirable to build a classifier that is bounded within an interval. Our motivating example is rooted in monitoring in a stamping process. A novel approach is proposed and examined in this paper. Our method consists of three stages: (1) A baseline of each class is estimated via convex optimization; (2) An “optimal interval” that maximizes the difference among the baselines is identified; (3) A classifier that is based on the “optimal interval” is constructed. We analyze the implementation strategy and properties of the derived algorithm. The derived classifier is named an interval based classifier (IBC) and can be computed via a low-order-of-complexity algorithm. Comparing to existing state-of-the-art classifiers, we illustrate the advantages of our approach. To showcase its usage in applications, we apply the IBC to a set of tonnage curves from stamping processes, and observed superior performance. This method can help identifying faulty situations in manufacturing. The computational steps of IBC take advantage of operations-research methodology. IBC can serve as a general data mining tool, when the features are based on single intervals.