An efficient algorithm for the parametric resource allocation problem

The parametric resource allocation problem asks to minimize the sum of separable single-variable convex functions containing a parameter λ, Σ_{i = 1}ⁿ (ƒ_i(x_i + λg_i(x_i)), under simple constraints Σ_{i = 1}ⁿ x_i = M, l_i≤x_i≤u_i and x_i: nonnegative integers for i = 1, 2, …, n, where M is a given positive integer, and l_i and u_i are given lower and upper bounds on x_i. This paper presents an efficient algorithm for computing the sequence of all optimal solutions when λ is continuously changed from 0 to ∞. The required time is O(G√Mlog² n + n log n + n log(M/n)), where G = Σ_{i = 1}ⁿ u_i − Σ_{i = 1n} l_i and an evaluation of ƒ_i(·) or g_i(·) is assumed to be done in constant time.     

Boundedness and asymptotic behavior of the solutions of a fuzzy difference equation

In this paper we study the existence, the uniqueness, the boundedness and the asymptotic behavior of the positive solutions of the fuzzy difference equation x_n+1=∑_i=0^kA_i/x_n−i^p_i, where k{1,2,…,}, A_i, i{0,1,…,k}, are positive fuzzy numbers, p_i, i{0,1,…,k}, are positive constants and x_i, i{−k,−k+1,…,0}, are positive fuzzy numbers.     

Cycle decompositions of crowns

For an integer n3, the crown S_n⁰ is defined to be the graph with vertex set {x₀,x₁,…,x_n−1,y₀,y₁,…,y_n−1} and edge set {x_iy_j: 0i,jn−1, i≠j}. In this paper we give some sufficient conditions for the edge decomposition of the crown into isomorphic cycles.     

Extremal properties of strong quadrature weights and maximal mass results for truncated strong moment problems

A bisequence of complex numbers {μ_n}_−∞^∞ determines a strong moment functional satisfying L[xⁿ] = μ_n. If is positive-definite on a bounded interval (a,b) R{0}, then has an integral representation , n=0, ±1, ±2,…, and quadrature rules {w_ni,x_ni} exist such that μ_k = ∑_i=i^n_ns_ni^kw_ni. This paper is concerned with establishing certain extremal properties of the weights w_ni and using these properties to obtain maximal mass results satisfied by distributions ψ(x) representing when only a finite bisequence of moments {μ_k}_k=−nⁿ⁻¹ is given.     

Combinatorial theorems on contractive mappings in power sets

We prove that to every positive integer n there exists a positive integer h such that the following holds: If S is a set of h elements and ƒ a mapping of the power set of S into such that ƒ(T)T for all T , then there exists a strictly increasing sequence T₁T_n of subsets of S such that one of the following three possibilities holds: (a) all sets ƒ(T_i), i= 1,…,n, are equal; (b) for all i=1,…, n, we have ƒ(T_i)=T_i; (c) T_i=ƒ(T_i+1) for all i= 1,…,n-1. This theorem generalizes theorems of the author, Rado, and Leeb. It has applications for subtrees in power sets.     

Oscillation criteria for first-order neutral nonlinear difference equations with variable coefficients

Consider the first-order neutral nonlinear difference equation of the form

, where τ > 0, σ_i ≥ 0 (i = 1, 2,…, m) are integers, {p_n} and {q_n} are nonnegative sequences. We obtain new criteria for the oscillation of the above equation without the restrictions Σ_n=0^∞ q_n = ∞ or Σ_n=0^∞ nq_n Σ_j=n^∞ q_j = ∞ commonly used in the literature.     

A Helly theorem for geodesic convexity in strongly dismantlable graphs

A (finite or infinite) graph G is strongly dismantlable if its vertices can be linearly ordered x₀,…, x so that, for each ordinal β < , there exists a strictly increasing finite sequence (i_j)_{0 j n} of ordinals such that i₀ = β, i_n = and x_ij+1 is adjacent with x_ij and with all neighbors of x_ij in the subgraph ofG induced by {x_y: β γ }. We show that the Helly number for the geodesic convexity of such a graph equals its clique number. This generalizes a result of Bandelt and Mulder (1990) for dismantlable graphs. We also get an analogous equality dealing with infinite families of convex sets.     

On the area of the intersection of disks in the plane

Let C₁,…, C_n and C′₁,…, C′_n be two collections of equal disks in the plane, with centers c₁,…, c_n and c′₁,…, c′_n. According to a well-known conjecture of Klee and Wagon (1991), if |c_i − c_j| ≥ |c′_i − c′_j| for all i, j, then Area(∩_i C_i) ≤ Area(∩_i C′_i).

We prove this statement in the special case when there is a continuous contraction of {c₁,…, c_n} onto {c′₁,…, c′_n}.     

A note on linearization of actions of finitely semisimple Hopf algebras on local algebras

Let H be a Hopf algebra over a field k and let H A → A, h a → h.a, be an action of H on a commutative local Noetherian kalgebra (A, m). We say that this action is linearizable if there exists a minimal system x₁, …, x_n of generators of the maximal ideal m such that h.x_i ε kx₁ + …+ kx_n for all h ε H and i = 1, …, n. In the paper we prove that the actions from a certain class are linearizable (see Theorem 4), and we indicate some consequences of this fact.     

A generalization of carathéodory''s theorem

The following theorem is proved. If the sets and a εⁿ⁺¹_i=1 conv V_i, then there exist elements v_i ε V_i (i=1…,n+1) such that a ε conv{v₁,…,v_n+1}. This is generalization of Carathéodory's theorem. By applying this and similar results some open questions are answered.     

Multicolored forests in complete bipartite graphs

If the edges of a graph G are colored using k colors, we consider the color distribution for this coloring a=(a₁,a₂,…,a_k), in which a_i denotes the number of edges of color i for i=1,2,…,k. We find inequalities and majorization conditions on color distributions of the complete bipartite graph K_n,n which guarantee the existence of multicolored subgraphs: in particular, multicolored forests and trees. We end with a conjecture on partitions of K_n,n into multicolored trees.     

Intersections of nest algebras in finite dimensions

If are maximal nests on a finite-dimensional Hilbert space H, the dimension of the intersection of the corresponding nest algebras is at least dim H. On the other hand, there are three maximal nests whose nest algebras intersect in the scalar operators. The dimension of the intersection of two nest algebras (corresponding to maximal nests) can be of any integer value from n to n(n+1)/2, where n=dim H. For any two maximal nests there exists a basis {f₁,f₂,…,f_n} of H and a permutation π such that and where M_i=  span{f₁,f₂,…,f_i} and N_i= span{f_π(1),f_π(2),…,f_π(i)}. The intersection of the corresponding nest algebras has minimum dimension, namely dim H, precisely when π(j)=n−j+1,1jn. Those algebras which are upper-triangular matrix incidence algebras, relative to some basis, can be characterised as intersections of certain nest algebras.     

Efficient robust estimation of parameter in the random censorship model

For an open set Θ of ^k, let \s{P_θ: θ Θ\s} be a parametric family of probabilities modeling the distribution of i.i.d. random variables X₁,…, X_n. Suppose X_i's are subject to right censoring and one is only able to observe the pairs (min(X_i, Y_i), [X_i Y_i]), i = 1,…, n, where [A] denotes the indicator function of the event A, Y₁,…, Y_n are independent of X₁,…, X_n and i.i.d. with unknown distribution Q₀. This paper investigates estimation of the value θ that gives a fitted member of the parametric family when the distributions of X₁ and Y₁ are subject to contamination. The constructed estimators are adaptive under the semi-parametric model and robust against small contaminations: they achieve a lower bound for the local asymptotic minimax risk over Hellinger neighborhoods, in the Hájel—Le Cam sense. The work relies on Beran (1981). The construction employs some results on product-limit estimators.     

A parallel computing scheme for minimizing a class of large scale functions

This paper gives a parallel computing scheme for minimizing a twice continuously differentiable function with the form

where x = (x^T₁,…,x^T_m)^T and x_i R^n_i, ∑^m_{i = 1}n_i = n, and n a very big number. It is proved that we may use m parallel processors and an iterative procedure to find a minimizer of ƒ(x). The convergence and convergence rate are given under some conditions. The conditions for finding a global minimizer of ƒ(x by using this scheme are given, too. A similar scheme can also be used parallelly to solve a large scale system of nonlinear equations in the similar way. A more general case is also investigated.     

Polyhedral graphs with extreme numbers of types of faces

A face F of a polyhedral graph G(V,E,F) is an a₁,a₂,…,a_l-face if is an l-gon and the degrees d(x_i) of the vertices x_iV incident with in the cyclic order are a_i,i=1,2,…,l. The lexicographic minimum b₁,b₂,…,b_l such that is a b₁,b₂,…,b_l-face is the type of . All polyhedral graphs having only one type of faces are listed. It is proved that the set of triangulations having only faces of different types is non-empty and finite.     

Loopless generation of up–down permutations

An up–down permutation P=(p₁,p₂,…,p_n) is a permutation of the integers 1 to n which satisfies constraints specified by a sequence C=(c₁,c₂,…,c_n−1) of U's and D's of length n−1. If c_i is U then p_i<p_i+1 otherwise p_i−1>p_i. A loopless algorithm is developed for generating all the up–down permutations satisfying any sequence C. Ranking and unranking algorithms are discussed.     

The existence of Schröder designs with equal-sized holes

A holey Schröder design of type h₁^n₁h₂^n₂ … h_k^n_k (HSD(h₁^n₁h₂^n₂ … h_k^n_k)) is equivalent to a frame idempotent Schröder quasigroup (FISQ(h₁^n₁h₂^n₂ … h_k^n_k)) of order n with n_i missing subquasigroups (holes) of order h_i, (1 i k), which are disjoint and spanning, that is, Σ_{1 i k} n_ih_i = n. In this paper, it is shown that an HSD(hⁿ) exists if and only if h²n(n − 1) 0 (mod 4) with expceptions (h, n) ε {{(1,5),(1,9),(2,4)}} and the possible exception of (h, n) = (6,4).     

A dense planar point set from iterated line intersections

Given S₁, a starting set of points in the plane, not all on a line, we define a sequence of planar point sets {S_i}_i=1^∞ as follows. With S_i already determined, let L_i be the set of all the lines determined by pairs of points from S_i, and let S_i+1 be the set of all the intersection points of lines in L_i. We show that with the exception of some very particular starting configurations, the limiting point set _i=1^∞S_i is everywhere dense in the plane.     

Weak convergence to the multiple Stratonovich integral

We have considered the problem of the weak convergence, as tends to zero, of the multiple integral processes

in the space , where fL²([0,T]ⁿ) is a given function, and {η(t)}_>0 is a family of stochastic processes with absolutely continuous paths that converges weakly to the Brownian motion. In view of the known results when n2 and f(t₁,…,t_n)=1_{t1<t2<<tn}, we cannot expect that these multiple integrals converge to the multiple Itô–Wiener integral of f, because the quadratic variations of the η are null. We have obtained the existence of the limit for any {η}, when f is given by a multimeasure, and under some conditions on {η} when f is a continuous function and when f(t₁,…,t_n)=f₁(t₁)f_n(t_n)1_{t1<t2<<tn}, with f_iL²([0,T]) for any i=1,…,n. In all these cases the limit process is the multiple Stratonovich integral of the function f.     

Krylov subspace methods for eigenvalues with special properties and their analysis for normal matrices

In this paper we propose a general approach by which eigenvalues with a special property of a given matrix A can be obtained. In this approach we first determine a scalar function ψ: C → C whose modulus is maximized by the eigenvalues that have the special property. Next, we compute the generalized power iterations uinj + 1 = ψ(A)u_j, j = 0, 1,…, where u₀ is an arbitrary initial vector. Finally, we apply known Krylov subspace methods, such as the Arnoldi and Lanczos methods, to the vector u_n for some sufficiently large n. We can also apply the simultaneous iteration method to the subspace span{x⁽ⁿ⁾₁,…,x⁽ⁿ⁾_k} with some sufficiently large n, where x^(j+1)_m = ψ(A)x^(j)_m, j = 0, 1,…, m = 1,…, k. In all cases the resulting Ritz pairs are approximations to the eigenpairs of A with the special property. We provide a rather thorough convergence analysis of the approach involving all three methods as n → ∞ for the case in which A is a normal matrix. We also discuss the connections and similarities of our approach with the existing methods and approaches in the literature.