Bounds for non‐periodic mixtures of infinitely many materials

We prove bounds on the homogenized coefficients for general non‐periodic mixtures of an arbitrary number of isotropic materials, in the heat conduction framework. The component materials and their proportions are given through the Young measure associated to the sequence of coefficient functions. Upper and lower bounds inequalities are deduced in terms of algebraic relations between this Young measure and the eigenvalues of the H‐limit matrix. The proofs employ arguments of compensated compactness and fine properties of Young measures. When restricted to the periodic case, we recover known bounds. Copyright © 2005 John Wiley & Sons, Ltd.     

Bounds for Covering Codes over Large Alphabets

Let K_q(n,R) denote the minimum number of codewords in any q-ary code of length n and covering radius R. We collect lower and upper bounds for K_q(n,R) where 6 ≤ q ≤ 21 and R ≤ 3. For q ≤ 10, we consider lengths n ≤ 10, and for q ≥ 11, we consider n ≤ 8. This extends earlier results, which have been tabulated for 2 ≤ q ≤ 5. We survey known bounds and obtain some new results as well, also for s-surjective codes, which are closely related to covering codes and utilized in some of the constructions.AMS Classification: 94B75, 94B25, 94B65Gerzson Kéri - Supported in part by the Hungarian National Research Fund, Grant No. OTKA-T029572.Patric R. J. Östergård - Supported in part by the Academy of Finland, Grants No. 100500 and No. 202315.     

Finite element approximation of a semilinear elliptic problem with a singular nonlinearity

Given , we consider the following problem: find , such that where or 3, and in . We prove and error bounds for the standard continuous piecewise linear Galerkin finite element approximation with a (weakly) acute triangulation. Our bounds are nearly optimal. In addition, for d = 1 and 2 and we analyze a more practical scheme involving numerical integration on the nonlinear term. We obtain nearly optimal and error bounds for d = 1. For this case we also present some numerical results. Received July 4, 1996 / Revised version received December 18, 1997     

Continuity theorems for the M/M/1/n queueing system

In this paper continuity theorems are established for the number of losses during a busy period of the M/M/1/n queue. We consider an M/GI/1/n queueing system where the service time probability distribution, slightly different in a certain sense from the exponential distribution, is approximated by that exponential distribution. Continuity theorems are obtained in the form of one or two-sided stochastic inequalities. The paper shows how the bounds of these inequalities are changed if further assumptions, associated with specific properties of the service time distribution (precisely described in the paper), are made. Specifically, some parametric families of service time distributions are discussed, and the paper establishes uniform estimates (given for all possible values of the parameter) and local estimates (where the parameter is fixed and takes only the given value). The analysis of the paper is based on the level crossing approach and some characterization properties of the exponential distribution. Dedicated to Vladimir Mikhailovich Zolotarev, Victor Makarovich Kruglov, and to the memory of Vladimir Vyacheslavovich Kalashnikov.     

The two-dimensional finite bin packing problem. Part I: New lower bounds for the oriented case

The Two-Dimensional Finite Bin Packing Problem (2BP) consists of determining the minimum number of large identical rectangles, bins, that are required for allocating without overlapping a given set of rectangular items. The items are allocated into a bin with their edges always parallel or orthogonal to the bin edges. The problem is strongly NP-hard and finds many practical applications. In this paper we describe new lower bounds for the 2BP where the items have a fixed orientation and we show that the new lower bounds dominate two lower bounds proposed in the literature. These lower bounds are extended in Part II (see Boschetti and Mingozzi 2002) for a more general version of the 2BP where some items can be rotated by . Moreover, in Part II a new heuristic algorithm for solving both versions of the 2BP is presented and computational results on test problems from the literature are given in order to evaluate the effectiveness of the proposed lower bounds.     

矩阵Hadamard积和Fan积的特征值界的一些新估计式

本文研究了非奇异M-矩阵A与B的Fan积的最小特征值下界和非负矩阵A与B的Hadamard积 的谱半径上界的估计问题.利用Brauer定理,得到了一些只依赖于矩阵的元素且易于计算的新估计式,改进 了文献[4]现有的一些结果.     

Undetected error probability of q-ary constant weight codes

In this paper, we introduce a new combinatorial invariant called q-binomial moment for q-ary constant weight codes. We derive a lower bound on the q-binomial moments and introduce a new combinatorial structure called generalized (s, t)-designs which could achieve the lower bounds. Moreover, we employ the q-binomial moments to study the undetected error probability of q-ary constant weight codes. A lower bound on the undetected error probability for q-ary constant weight codes is obtained. This lower bound extends and unifies the related results of Abdel-Ghaffar for q-ary codes and Xia-Fu-Ling for binary constant weight codes. Finally, some q-ary constant weight codes which achieve the lower bounds are found.      

New convergence results on the global GMRES method for diagonalizable matrices

In the present paper, we give some new convergence results of the global GMRES method for multiple linear systems. In the case where the coefficient matrix A is diagonalizable, we derive new upper bounds for the Frobenius norm of the residual. We also consider the case of normal matrices and we propose new expressions for the norm of the residual.     

Strong bounds on perturbations

This paper provides strong bounds on perturbations over a collection of independent random variables, where ‘strong’ has to be understood as uniform w.r.t. some functional norm. Our analysis is based on studying the concept of weak differentiability. By applying a fundamental result from the theory of Banach spaces, we show that weak differentiability implies norm Lipschitz continuity. This result leads to bounds on the sensitivity of finite products of probability measures, in norm sense. We apply our results to derive bounds on perturbations for the transient waiting times in a G/G/1 queue. This research is supported by the Technology Foundation STW, applied science division of NWO and the technology programme of the Ministry of Economic Affairs.     

On binary linear <Emphasis Type="Italic">r</Emphasis>-identifying codes

A subspace C of the binary Hamming space F ⁿ of length n is called a linear r-identifying code if for all vectors of F ⁿ the intersections of C and closed r-radius neighbourhoods are nonempty and different. In this paper, we give lower bounds for such linear codes. For radius r =  2, we give some general constructions. We give many (optimal) constructions which were found by a computer search. New constructions improve some previously known upper bounds for r-identifying codes in the case where linearity is not assumed.     

加权流形上加权p-Laplace特征值问题的第一特征值下界估计

本文研究了加权流形上加权p-Laplacian特征值问题的第一特征值下界估计的问题.利用余面积公式、Cavalieri原理以及Federer-Fleming定理,获得了由Cheeger常数或等周常数确定的第一特征值的下界估计.     

Scattering by a highly oscillating surface

The boundary function method [A. B. Vasil'eva, V. F. Butuzov, and L. V. Kalachev, The boundary function method for singular perturbation problems, SIAM Studies in Applied Mathematics, Philadelphia, 1995] is used to build an asymptotic expansion at any order of accuracy of a scalar time‐harmonic wave scattered by a perfectly reflecting doubly periodic surface with oscillations at small and large scales. Error bounds are rigorously established, in particular in an optimal way on the relevant part of the field. It is also shown how the maximum principle can be used to design a homogenized surface whose reflected wave yields a first‐order approximation of the actual one. The theoretical derivations are illustrated by some numerical experiments, which in particular show that using the homogenized surface outperforms the usual approach consisting in setting an effective boundary condition on a flat boundary. Copyright © 2014 John Wiley & Sons, Ltd.     

Curves with Many Points and Multiplication Complexity in Any Extension of q

From the existence of algebraic function fields having some good properties, we obtain some new upper bounds on the bilinear complexity of multiplication in all extensions of the finite field _q, where q is an arbitrary prime power. So we prove that the bilinear complexity of multiplication in the finite fields _qⁿ is linear uniformly in q with respect to the degree n.     

On some sharp bounds for the homogenized p-poisson equation

We consider homogenization of a scale of p-Poisson equations in R^N. Some new bounds of the effective energy are proved and compared with the non-linear Wiener -and Hashin-Shtrikman bounds. Moreover, we point out concrete nontrivid examples where these bounds even coincide. Some new examples of “optimal” microstructures are presented.     

On L 1 Bounds for Asymptotic Normality of Some Weakly Dependent Random Variables

In the present paper, we consider L ₁ bounds for asymptotic normality for the sequence of r.v.’s X ₁,X ₂,… (not necessarily stationary) satisfying the ψ-mixing condition. The L ₁ bounds have been obtained in terms of Lyapunov fractions which, in a particular case, under finiteness of the third moments of summands and the finiteness of ∑ _r≥1 r ² ψ(r), are of order O(n ^−1/2), where the function ψ participates in the definition of the ψ-mixing condition.      

Improvement of the formal and numerical estimation of the constant in some Markov-Bernstein inequalities

Some methods of numerical analysis, used for obtaining estimations of zeros of polynomials, are studied again, more especially in the case where the zeros of these polynomials are all strictly positive, distinct and real. They give, in particular, formal lower and upper bounds for the smallest zero. Thanks to them, we produce new formal lower and upper bounds of the constant in Markov-Bernstein inequalities in L ² for the norm corresponding to the Laguerre and Gegenbauer inner products. In fact, since this constant is the inverse of the square root of the smallest zero of a polynomial, we give formal lower and upper bounds of this zero. Moreover, a new sufficient condition is given in order that a polynomial has some complex zeros. This revised version was published online in June 2006 with corrections to the Cover Date.     

On Lower Bounds for the L 1-Norm of Exponential Sums

In the paper a method for finding lower bounds of the L ₁-norm of some exponential sums is described.     

Convexification of a Noninferior Frontier

In a recent paper by Li (Ref. 1), a scheme was proposed to convexify an efficient frontier for a vector optimization problem by rescaling each component of the vector objective functions by its p-power. For sufficiently large p, it was shown that the transformed efficient frontier is cone-convex; hence, the usual linear scalarization (or supporting hyperplane) method can be used to find the efficient solutions. An outstanding question remains: What is the minimum value of p such that the efficient frontier can be convexified? In this note, we answer the above question by deriving some theoretical lower bounds for p.

     

A Linear Algebraic Approach to Metering Schemes

A metering scheme is a method by which an audit agency is able to measure the interaction between servers and clients during a certain number of time frames. Naor and Pinkas (Vol. 1403 of LNCS, pp. 576–590) proposed metering schemes where any server is able to compute a proof (i.e., a value to be shown to the audit agency at the end of each time frame), if and only if it has been visited by a number of clients larger than or equal to some threshold h during the time frame. Masucci and Stinson (Vol. 1895 of LNCS, pp. 72–87) showed how to construct a metering scheme realizing any access structure, where the access structure is the family of all subsets of clients which enable a server to compute its proof. They also provided lower bounds on the communication complexity of metering schemes. In this paper we describe a linear algebraic approach to design metering schemes realizing any access structure. Namely, given any access structure, we present a method to construct a metering scheme realizing it from any linear secret sharing scheme with the same access structure. Besides, we prove some properties about the relationship between metering schemes and secret sharing schemes. These properties provide some new bounds on the information distributed to clients and servers in a metering scheme. According to these bounds, the optimality of the metering schemes obtained by our method relies upon the optimality of the linear secret sharing schemes for the given access structure.     

On Small and Large Hyperplanes of DW(5, q)

We determine lower and upper bounds for the size of a hyperplane of the dual polar space DW(5, q). In some cases, we also determine all hyperplanes attaining these bounds.