Second order properties of queues are important in design and analysis of service systems. In this paper we show that the blocking probability of M/M/C/N queue is increasing directionally convex in (λ,?μ), where λ is arrival rate and μ is service rate. To illustrate the usefulness of this result we consider a heterogeneous queueing system with non-stationary arrival and service processes. The arrival and service rates alternate between two levels (λ1,μ1) and (λ2,μ2), spending an exponentially distributed amount of time with rate cα i in level i, i=1,2. When the system is in state i, the arrival rate is λ i and the service rate is μ i . Applying the increasing directional convexity result we show that the blocking probability is decreasing in c, extending a result of Fond and Ross [7] for the case C=N=1.
相似文献We consider a general k-dimensional discounted infinite server queueing process (alternatively, an incurred but not reported claim process) where the multivariate inputs (claims) are given by a k-dimensional finite-state Markov chain and the arrivals follow a renewal process. After deriving a multidimensional integral equation for the moment-generating function jointly to the state of the input at time t given the initial state of the input at time 0, asymptotic results for the first and second (matrix) moments of the process are provided. In particular, when the interarrival or service times are exponentially distributed, transient expressions for the first two moments are obtained. Also, the moment-generating function for the process with deterministic interarrival times is considered to provide more explicit expressions. Finally, we demonstrate the potential of the present model by showing how it allows us to study semi-Markovian modulated infinite server queues where the customers (claims) arrival and service (reporting delay) times depend on the state of the process immediately before and at the switching times.
相似文献1. |
A deterministic black-box identity testing algorithm for ΣΠΣ(k; d;ρ) circuits that runs in quasi-polynomial time (for ρ=polylog(n+d)). In particular this gives the first black-box quasi-polynomial time PIT algorithm for depth-3 circuits with k multiplication gates. 相似文献
13.
Summary The existence of a joint asymptotic distribution for the windings of a three-dimensional Brownian motion around a finite number of straight lines is obtained. This complements the recent studies, by Pitman- Yor, and the authors, of the joint asymptotic distribution for the windings of planar Brownian motion around a finite number of points.The following principle governs the passage from results in the plane to results in space:Let B be a three-dimensional Brownian motion, and P
1, ..., P
k, k planes which intersect two by two. Then, the convergences in distribution concerning the planar Brownian motions B
i (1ik), defined respectively as the orthogonal projections of B on P
i (1ik), take place jointly, and the corresponding limit variables are independent. 相似文献
14.
In 2000, Enomoto and Ota [J Graph Theory 34 (2000), 163–169] stated the following conjecture. Let G be a graph of order n, and let n1, n2, …, nk be positive integers with \begin{eqnarray*}\sum\nolimits_{{{i}} = {{1}}}^{{{k}}} {{n}}_{{{i}}} = {{n}}\end{eqnarray*}. If σ2(G)≥n+ k?1, then for any k distinct vertices x1, x2, …, xk in G, there exist vertex disjoint paths P1, P2, …, Pk such that |Pi|=ni and xi is an endpoint of Pi for every i, 1≤i≤k. We prove an asymptotic version of this conjecture in the following sense. For every k positive real numbers γ1, …, γk with \begin{eqnarray*}\sum\nolimits_{{{i}} = {{1}}}^{{{k}}} \gamma_{{{i}}} = {{1}}\end{eqnarray*}, and for every ε>0, there exists n0 such that for every graph G of order n≥n0 with σ2(G)≥n+ k?1, and for every choice of k vertices x1, …, xk∈V(G), there exist vertex disjoint paths P1, …, Pk in G such that \begin{eqnarray*}\sum\nolimits_{{{i}} = {{1}}}^{{{k}}} |{{P}}_{{{i}}}| = {{n}}\end{eqnarray*}, the vertex xi is an endpoint of the path Pi, and (γi?ε)n<|Pi|<(γi + ε)n for every i, 1≤i≤k. © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 37–51, 2010 相似文献
15.
Let G be a graph of order n, and n = Σki=1 ai be a partition of n with ai ≥ 2. In this article we show that if the minimum degree of G is at least 3k−2, then for any distinct k vertices v1,…, vk of G, the vertex set V(G) can be decomposed into k disjoint subsets A1,…, Ak so that |Ai| = ai,viisAi is an element of Ai and “the subgraph induced by Ai contains no isolated vertices” for all i, 1 ≥ i ≥ k. Here, the bound on the minimum degree is sharp. © 1997 John Wiley & Sons, Inc. 相似文献
16.
Sang-Eon Han 《Acta Appl Math》2010,110(2):921-944
Recent papers have partially discussed the multiplicative or the non-multiplicative property of the digital fundamental group.
Thus, the paper studies a condition of which the multiplicative property of the digital fundamental group holds. Precisely,
for two digital spaces with k
i
-adjacencies of
Zni\mathbf{Z}^{n_{i}}
, denoted by (X
i
,k
i
), i∈{1,2}, using the L
HS- or L
HC-property of the digital product (or Cartesian product of digital spaces) with k-adjacency (X
1×X
2,k), a k-homotopic thinning of the digital product, and various properties from digital covering and digital homotopy theories, we
provide a method of calculating the k-fundamental group of the digital product. Furthermore, the notion of HT-(k
0,k
1)-isomorphism is established and used in calculating the k-fundamental group of a digital product. Finally, we find a condition of which the multiplicative property of the digital
fundamental group holds. This property can be used in classifying digital spaces from the view points of digital homotopy
theory, mathematical morphology, and digital geometry. 相似文献
17.
Andreas Brandst?dt Martin Charles Golumbic Van Bang Le Marina Lipshteyn 《Graphs and Combinatorics》2011,27(6):799-819
In this paper, we introduce the notion of path-bicolorability that generalizes bipartite graphs in a natural way: For k ≥ 2, a graph G = (V, E) is P
k
-bicolorable if its vertex set V can be partitioned into two subsets (i.e., color classes) V
1 and V
2 such that for every induced P
k
(a path with exactly k − 1 edges and k vertices) in G, the two colors alternate along the P
k
, i.e., no two consecutive vertices of the P
k
belong to the same color class V
i
, i = 1, 2. Obviously, a graph is bipartite if and only if it is P
2-bicolorable. We give a structural characterization of P
3-bicolorable graphs which also implies linear time recognition of these graphs. Moreover, we give a characterization of P
4-bicolorable graphs in terms of forbidden subgraphs. 相似文献
18.
Remco van der Hofstad 《Random Structures and Algorithms》2013,42(4):480-508
We study the critical behavior of inhomogeneous random graphs in the so‐called rank‐1 case, where edges are present independently but with unequal edge occupation probabilities. The edge occupation probabilities are moderated by vertex weights, and are such that the degree of vertex i is close in distribution to a Poisson random variable with parameter wi, where wi denotes the weight of vertex i. We choose the weights such that the weight of a uniformly chosen vertex converges in distribution to a limiting random variable W. In this case, the proportion of vertices with degree k is close to the probability that a Poisson random variable with random parameter W takes the value k. We pay special attention to the power‐law case, i.e., the case where \begin{align*}{\mathbb{P}}(W\geq k)\end{align*} is proportional to k‐(τ‐1) for some power‐law exponent τ > 3, a property which is then inherited by the asymptotic degree distribution. We show that the critical behavior depends sensitively on the properties of the asymptotic degree distribution moderated by the asymptotic weight distribution W. Indeed, when \begin{align*}{\mathbb{P}}(W > k) \leq ck^{-(\tau-1)}\end{align*} for all k ≥ 1 and some τ > 4 and c > 0, the largest critical connected component in a graph of size n is of order n2/3, as it is for the critical Erd?s‐Rényi random graph. When, instead, \begin{align*}{\mathbb{P}}(W > k)=ck^{-(\tau-1)}(1+o(1))\end{align*} for k large and some τ∈(3,4) and c > 0, the largest critical connected component is of the much smaller order n(τ‐2)/(τ‐1). © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 42, 480–508, 2013 相似文献
19.
E. R. Lamken 《组合设计杂志》2009,17(6):425-447
Two resolutions R and R′ of a combinatorial design are called orthogonal if |Ri∩R|≤1 for all Ri∈R and R∈R′. A set Q={R1, R2, …, Rd} of d resolutions of a combinatorial design is called a set of mutually orthogonal resolutions (MORs) if the resolutions of Q are pairwise orthogonal. In this paper, we establish necessary and sufficient conditions for the asymptotic existence of a (v, k, 1)‐BIBD with d mutually orthogonal resolutions for d≥2 and k≥3 and necessary and sufficient conditions for the asymptotic existence of a (v, k, k?1)‐BIBD with d mutually orthogonal near resolutions for d≥2 and k≥3. We use complementary designs and the most general form of an asymptotic existence theorem for decompositions of edge‐colored complete digraphs into prespecified edge‐colored subgraphs. © 2009 Wiley Periodicals, Inc. J Combin Designs 17: 425–447, 2009 相似文献
20.
Covering arrays have applications in software, network and circuit testing. In this article, we consider a generalization of covering arrays that allows mixed alphabet sizes as well as a graph structure that specifies the pairwise interactions that need to be tested. Let k and n be positive integers, and let G be a graph with k vertices v1,v2,…, vk with respective vertex weights g1 ≤ g2 ≤ … ≤ gk. A mixed covering array on G, denoted by , is an n × k array such that column i corresponds to vi, cells in column i are filled with elements from ?gi and every pair of columns i,j corresponding to an edge vi,vj in G has every possible pair from ?gi × ?gj appearing in some row. The number of rows in such array is called its size. Given a weighted graph G, a mixed covering array on G with minimum size is called optimal. In this article, we give upper and lower bounds on the size of mixed covering arrays on graphs based on graph homomorphisms. We provide constructions for covering arrays on graphs based on basic graph operations. In particular, we construct optimal mixed covering arrays on trees, cycles and bipartite graphs; the constructed optimal objects have the additional property of being nearly point balanced. © 2007 Wiley Periodicals, Inc. J Combin Designs 15: 393–404, 2007 相似文献
|