A note on an optimal choice problem

An item has probabilityp ₀ of not being workable. Before, going into use it has to be controlled by some deliberately chosen checksC _i which costsc _i 0,1in. Total checking costs must be not larger thanc ₀>0. It may happen that a check breaks a workable item, and failures may be overlooked. The problem is to determine an optimal sequence of checks subject to the cost constraints, such that the probability is maximized that an item leaving the checks is workable. In [1] this problem is solved by W. Stadje, but numerically the solution method only is applicable to problems of modest size.In this paper a simple reformulation of the original problem is presented. This first allows a simpler derivation of some of the results in [1]. Further, a dynamic programming algorithm is presented, which is pseudopolynomial, if costsc _i are integers. It then requiresO(n·c ₀) time.     

On the existence of convex decompositions of partially separable functions

The concept of a partially separable functionf developed in [4] is generalized to include all functionsf that can be expressed as a finite sum of element functionsf _i whose Hessians have nontrivial nullspacesN _i , Such functions can be efficiently minimized by the partitioned variable metric methods described in [5], provided that each element functionf _i is convex. If this condition is not satisfied, we attempt toconvexify the given decomposition by shifting quadratic terms among the originalf _i such that the resulting modified element functions are at least locally convex. To avoid tests on the numerical value of the Hessian, we study the totally convex case where all locally convexf with the separability structureN _i ¹ have a convex decomposition. It is shown that total convexity only depends on the associated linear conditions on the Hessian matrix. In the sparse case, when eachN _i is spanned by Cartesian basis vectors, it is shown that a sparsity pattern corresponds to a totally convex structure if and only if it allows a (permuted) LDL^T factorization without fill-in.     

The generalized Banach match-box problem: Application in disc storage management

A computer system manages disc storage of finite capacity c blocks. This storage must be divided among N files in such a way that the expected number of disc accesses accomplished until the necessary reorganization is maximized. Each access to the disc appends a record of a fixed length to the ith file with probability p _i (i=1,h., N). The reorganization is needed when the chosen file has run out of space. It is shown that the above problem is a generalization of Banach's match-box problem known from the probability theory. A detailed separate analysis for the N=2 case and for the multivariate case is performed and some approximate results for large c are given.     

On the automatic derivation of a set of geometric formulae

Leta, b, andc be the three sides of a triangleABC, a _i ,b _i ,c _i anda _e ,b _e , c_e be the lengths of the three internal and external bisectors of the three anglesA, B, andC respectively. It is easy to express the bisectors as formulae of the sides. In this paper, we solve a problem proposed by H. Zassenhaus: for any three different bisectors in {a_i, b_i, c_i, a_e, b_e, c_e}, finding the relations between each side of the triangle and the three chosen bisectors. We also prove that given any general values for three different bisectors (internal or external) of a triangle, we can not draw the triangle using a ruler and a pair of compasses alone. The formulae mentioned above are derived automatically using a general method of mechanical formula derivation.This work was partially supported by a Grant from Chinese NSF and by the NSF Grant CCR-917870.     

Existence of a stationary symmetric solution of the two-dimensional Navier-Stokes equations with a given head and with nonzero fluxes

We consider a stationary boundary value problem for the Navier-Stokes equations of a homogeneous incompressible fluid in a two-dimensional bounded domain with boundary consisting of connected components Γ _i . On each part Γ _i , we specify the tangent component of the flow velocity vector, the total flow head (up to an additive constant), and the fluid flux through Γ _i . For the case in which the domain and the original data are symmetric around some line, we prove the existence of a solution of the problem with such a symmetry. We also present some results on the solvability in the nonsymmetric case.     

A Stochastic Directional Convexity Result and Its Application in Comparison of Queues

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 (λ₁,μ₁) and (λ₂,μ₂), 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.

     

On the asymptotic optimality of the <Emphasis Type="Italic">cμ</Emphasis>/<Emphasis Type="Italic">θ</Emphasis> rule under ergodic cost

We consider an overloaded multi-server multi-class queueing model where customers may abandon while waiting to be served. For class i, service is provided at rate μ _i , and abandonment occurs at rate θ _i . In a many-server fluid regime, we show that prioritizing the classes in decreasing order of c _i μ _i /θ _i asymptotically minimizes an ergodic holding cost, where c _i denotes the equivalent holding cost per unit time for class i.     

Consecutive colorings of graphs

In a simple graphG=(X.E) a positive integerc _i is associated with every nodei. We consider node colorings where nodei receives a setS(i) ofc _i consecutive colors andS(i)S(j)=Ø whenever nodesi andj are linked inG. Upper bounds on the minimum number of colors needed are derived. The case of perfect graphs is discussed.

---

Zusammenfassung In einem schlichten GraphenG=(X, E) gibt man jedem Knotenpunkti einen positiven ganzzahligen Wertc _i. Wir betrachten Färbungen der Knotenpunkte, bei denen jeder Knotenpunkti eine MengeS(i) vonc _i konsekutiven Farben erhält mitS(i)S(j)=Ø wenn die Kante [i.j] existiert. Obere Grenzen für die minimale Anzahl der Farben solcher Färbungen werden hergeleitet. Der Fall der perfekten Graphen wird auch kurz diskutiert.

     

Tail bounds for the height and width of a random tree with a given degree sequence

Fix a sequence c = (c₁,…,c_n) of non‐negative integers with sum n ? 1. We say a rooted tree T has child sequence c if it is possible to order the nodes of T as v₁,…,v_n so that for each 1 ≤ i ≤ n, v_i has exactly c_i children. Let ${\mathcal T}Fix a sequence c = (c₁,…,c_n) of non‐negative integers with sum n ? 1. We say a rooted tree T has child sequence c if it is possible to order the nodes of T as v₁,…,v_n so that for each 1 ≤ i ≤ n, v_i has exactly c_i children. Let ${\mathcal T}$ be a plane tree drawn uniformly at random from among all plane trees with child sequence c . In this note we prove sub‐Gaussian tail bounds on the height (greatest depth of any node) and width (greatest number of nodes at any single depth) of ${\mathcal T}$. These bounds are optimal up to the constant in the exponent when c satisfies $\sum_{i=1}^n c_i^2=O(n)$; the latter can be viewed as a “finite variance” condition for the child sequence. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012     

Varietà a congruenze ideali

Riassunto SiaX una classe di strutture algebriche simili,AA _i)_i∈I una famiglia di algebre diX eL _i il reticolo delle congruenze diA _i. In modo naturale ad ogni ideale di resta associata una congruenza di . Il concetto di ?congruenza ideale? cioè di congruenza diA legata a un ideale diL estende il concetto di ?congruenza filtrale? di congruenza cioè legata a un filtro suI. Ciò conduce a introdurre un concetto di ?classe ideale? di algebre che estende quello di ?classe filtrale? di [3]. Vengono estesi alle classi ideali i risultati di [3].

---

Summary LetX be a class of similar algebras, (A _i)_i∈I a family of algebras inX and letL _i be the lattice of the congruences ofA _i. In a natural way we can link each ideal ofL=IIL _i with a congruence ofA=IIA _i. So we are brought to consider ?ideal classes? of algebras wich are an extension of ?filtral classes? [3]. The results of [3] are extended to ?ideal classes?.

---

---

Lavoro eseguito nell'ambito dell'attività del Comitato Nazionale per la Matematica del C.N.R., contratto 115218205174, anno 1970.     

Moderate Deviations for Linear Processes Generated by Martingale-Like Random Variables

In this paper we study the moderate deviation principle for linear statistics of the type S _n =∑ _i∈Z c _n,i ξ _i , where c _n,i are real numbers, and the variables ξ _i are in turn stationary martingale differences or dependent sequences satisfying projective criteria. As an application, we obtain the moderate deviation principle and its functional form for sums of a class of linear processes with dependent innovations that might exhibit long memory. A new notion of equivalence of the coefficients allows us to study the difficult case where the variance of S _n behaves slower than n. The main tools are: a new type of martingale approximations and moment and maximal inequalities that are important in themselves.     

Online weighted flow time and deadline scheduling

In this paper we study some aspects of weighted flow time. We first show that the online algorithm Highest Density First is an O(1)-speed O(1)-approximation algorithm for P|r_i,pmtn|∑w_iF_i. We then consider a related Deadline Scheduling Problem that involves minimizing the weight of the jobs unfinished by some unknown deadline D on a uniprocessor. We show that any c-competitive online algorithm for weighted flow time must also be c-competitive for deadline scheduling. We then give an O(1)-competitive algorithm for deadline scheduling.     

Travelling front solution for a class of competition-diffusion system with high-order singular point

In this paper, the existence of travelling front solution for a class of competition-diffusion system with high-order singular point

1-Factorizations of cartesian products of regular graphs

Let G₁, G₂…, G_n be regular graphs and H be the Cartesian product of these graphs (H = G₁ × G₂ × … × G_n). The following will be proved: If the set {G₁, G₂…, G_n} has at leat one of the following properties: (*) for at leat one i ? {1, 2,…, n}, there exists a 1-factorization of G_i or (**) there exists at least two numbers i and j such that 1 ≤ i < j ≤ n and both the Graphs G_i and G_j contain at least one 1-factor, then there exists a 1-factorization of H. Further results: Let F be a cycle of length greater than three and let G be an arbitrary cubic graph. Then there exists a 1-factorization of the 5-regular graph H = F × G. The last result shows that neither (*) nor (**) is a necessary condition for the existence of a 1-factorization of a Cartesian product of regular graphs.     

Two New Classes of Difference Families

A Z-cyclic triplewhist tournament for 4n+1 players, or briefly a TWh(4n+1), is equivalent to a n-set {(a_i, b_i, c_i, d_i) | i=1, …, n} of quadruples partitioning Z_4n+1−{0} with the property that ⁿ_i=1 {±(a_i−c_i), ±(b_i−d_i)}=ⁿ_i=1 {±(a_i−b_i), ±(c_i−d_i)}=ⁿ_i=1 {±(a_i−d_i), ±(b_i−c_i)}=Z_4n+1−{0}. The existence problem for Z-cyclic TWh(p)'s with p a prime has been solved for p1 (mod 16). I. Anderson et al. (1995, Discrete Math.138, 31–41) treated the case of p≡5 (mod 8) while Y. S. Liaw (1996, J. Combin. Des.4, 219–233) and G. McNay (1996, Utilitas Math.49, 191–201) treated the case of p≡9 (mod 16). In this paper, besides giving easier proofs of these authors' results, we solve the problem also for primes p≡1 (mod 16). The final result is the existence of a Z-cyclic TWh(v) for any v whose prime factors are all≡1 (mod 4) and distinct from 5, 13, and 17.     

Rook numbers and the normal ordering problem

For an element w in the Weyl algebra generated by D and U with relation DU=UD+1, the normally ordered form is w=∑c_i,jUⁱD^j. We demonstrate that the normal order coefficients c_i,j of a word w are rook numbers on a Ferrers board. We use this interpretation to give a new proof of the rook factorization theorem, which we use to provide an explicit formula for the coefficients c_i,j. We calculate the Weyl binomial coefficients: normal order coefficients of the element (D+U)ⁿ in the Weyl algebra. We extend these results to the q-analogue of the Weyl algebra. We discuss further generalizations using i-rook numbers.     

Power series whose coefficients form homogeneous random processes

Summary Power series f(z) = a _izⁱ are considered, where the sequence {a _i} forms a homogeneous random process. If the sequence is exchangeable and the variance of the marginal distributions exists, it is proved that r, the random radius of convergence of f(z), takes the values 0 and 1. If the sequence is a second order stationary time series then r=1 with probability 1. If {a _i} is a regular denumerable Markov chain, it can be proved that r=c=1 with probability 1, but both c=0 and c=1 can arise. A number of criteria are given for deciding the value of c in this situation.     

Entropy maximization

It is shown that (i) every probability density is the unique maximizer of relative entropy in an appropriate class and (ii) in the class of all pdf f that satisfy ∝ fh _i dμ = λ _i for i = 1, 2, ..., ... kthe maximizer of entropy is an f ₀ that is proportional to exp(Σc _i h _i ) for some choice of c _i . An extension of this to a continuum of constraints and many examples are presented.     

On distance-regular graphs with fixed valency

We prove the following result. Let be a finite distance-regular graph. Letc _i ,a _i ,b _i be the intersection numbers of. If is not an ordinaryn-gon, then the number of (c _i ,a _i ,b _i ) such thatc _i =b _i is bounded by a certain function of the valencyk, say 10k2 ^k .Supported in part by N.S.F. grant MCS-830826. Also supported by Senior Visiting Scientist Grant of the British S.E.R.C. GR/C/97491 to visit Q.M.C. (University of London) 1984/5.Dedicated to Professor Hirosi Nagao on his 60th birthday     

Maximal σ‐polynomials of connected 3‐chromatic graphs

In the set of graphs of order n and chromatic number k the following partial order relation is defined. One says that a graph G is less than a graph H if c_i(G) ≤ c_i(H) holds for every i, k ≤ i ≤ n and at least one inequality is strict, where c_i(G) denotes the number of i‐color partitions of G. In this paper the first ? n/2 ? levels of the diagram of the partially ordered set of connected 3‐chromatic graphs of order n are described. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 210–222, 2003