Sharp probability bounds for the binomial moment problem with symmetry

Sharp bounds in terms of the first few binomial moments are found for the probability of a union of events, when the random variable denoting the number of events that occur follows symmetric distribution. Connection between the bounds of this paper and the bounds from a special case of the binomial moment problem of Prekopa (1995) is shown. As a special case, bounds for the probability when the underlying probability distribution is unimodal-symmetric are also found.     

离散时间代数Riccati方程的解矩阵的下界与上界

本文讨论离散时间代数Ｒｉｃｃａｔｉ方程ＡＴＸＡ－Ｘ－（ＡＴＸＢ＋Ｌ）（Ｒ＋ＢＴＸＢ）＾－１（ＬＴ＋ＢＴＸＡ）＋Ｑ＝０的唯一对称正定解的上界和下界。     

Power-law bounds on transfer matrices and quantum dynamics in one dimension-II

We establish quantum dynamical lower bounds for a number of discrete one-dimensional Schrödinger operators. These dynamical bounds are derived from power-law upper bounds on the norms of transfer matrices. We develop further the approach from part I and study many examples. Particular focus is put on models with finitely or at most countably many exceptional energies for which one can prove power-law bounds on transfer matrices. The models discussed in this paper include substitution models, Sturmian models, a hierarchical model, the prime model, and a class of moderately sparse potentials.     

Mixed volume techniques for embeddings of Laman graphs

Determining the number of embeddings of Laman graph frameworks is an open problem which corresponds to understanding the solutions of the resulting systems of equations. In this paper we investigate the bounds which can be obtained from the viewpoint of Bernstein's Theorem. The focus of the paper is to provide methods to study the mixed volume of suitable systems of polynomial equations obtained from the edge length constraints. While in most cases the resulting bounds are weaker than the best known bounds on the number of embeddings, for some classes of graphs the bounds are tight.     

A note on Schrage's generalised variable upper bounds

An improved procedure for implementing pivoting, based upon ideas from generalised upper bounds, is suggested for Schrage's generalised variable upper bounds.     

Bounds for aggregating nodes in network problems

It is often necessary or desirable in practice to replace a large, detailed optimization model with a smaller, approximate model. It would be useful to have bounds on the error resulting from this process of aggregation. This paper develops such bounds for a class of linear minimum-cost network-flow problems, where groups of nodes in a large problem are replaced by aggregate nodes. Two types of bounds are derived: A priori bounds are available before solving the aggregated problem; a posteriori bounds, which are generally tighter, may be computed afterwards.     

Enclosing clusters of zeros of polynomials

Lagrange interpolation and partial fraction expansion can be used to derive a Gerschgorin-type theorem that gives simple and powerful a posteriori error bounds for the zeros of a polynomial if approximations to all zeros are available. Compared to bounds from a corresponding eigenvalue problem, a factor of at least two is gained.The accuracy of the bounds is analyzed, and special attention is given to ensure that the bounds work well not only for single zeros but also for multiple zeros and clusters of close zeros.A Rouché-type theorem is also given, that in many cases reduces the bound even further.     

Analysis of upper bounds for the Pallet Loading Problem

This paper is concerned with upper bounds for the well-known Pallet Loading Problem (PLP), which is the problem of packing identical boxes into a rectangular pallet so as to maximize the number of boxes fitted. After giving a comprehensive review of the known upper bounds in the literature, we conduct a detailed analysis to determine which bounds dominate which others. The result is a ranking of the bounds in a partial order. It turns out that two of the bounds dominate all others: a bound due to Nelissen and a bound obtained from the linear programming relaxation of a set packing formulation. Experiments show that the latter is almost always optimal and can be computed quickly.     

Bounds for the largest Mahalanobis distance

Upper and lower bounds for the magnitude of the largest Mahalanobis distance, calculated from n multivariate observations of length p, are derived. These bounds are multivariate extensions of corresponding bounds that arise for the most deviant Z-score calculated from a univariate sample of size n. The approach taken is to pose optimization problems in a mathematical context and to employ variational methods to obtain solutions. The attainability of the bounds obtained is demonstrated. Bounds for related quantities (elements of the “hat matrix”) are also derived.     

Evaluating Improvements for Spacings of Order Statistics

We evaluate sharp upper bounds for the consecutive spacings of order statistics from an i.i.d. sample, measured in scale units generated by various central absolute moments of the parent distribution. The bounds are based on the projection method combined with the Hölder inequalities. We characterize the probability distributions for which the bounds are attained. We also evaluate the so obtained bounds numerically and compare them with other existing bounds.     

A new exact algorithm for the vehicle routing problem based onq-paths andk-shortest paths relaxations

We consider the basic Vehicle Routing Problem (VRP) in which a fleet ofM identical vehicles stationed at a central depot is to be optimally routed to supply customers with known demands subject only to vehicle capacity constraints. In this paper, we present an exact algorithm for solving the VRP that uses lower bounds obtained from a combination of two relaxations of the original problem which are based on the computation ofq-paths andk-shortest paths. A set of reduction tests derived from the computation of these bounds is applied to reduce the size of the problem and to improve the quality of the bounds. The resulting lower bounds are then embedded into a tree-search procedure to solve the problem optimally. Computational results are presented for a number of problems taken from the literature. The results demonstrate the effectiveness of the proposed method in solving problems involving up to about 50 customers and in providing tight lower bounds for problems up to about 150 customers.     

Upper and Lower Bounds for the Lengths of Steiner Trees in 3-Space

We present a method of determining upper and lower bounds for the length of a Steiner minimal tree in 3-space whose topology is a given full Steiner topology, or a degenerate form of that full Steiner topology. The bounds are tight, in the sense that they are exactly satisfied for some configurations. This represents the first nontrivial lower bound to appear in the literature. The bounds are developed by first studying properties of Simpson lines in both two and three dimensional space, and then introducing a class of easily constructed trees, called midpoint trees, which provide the upper and lower bounds. These bounds can be constructed in quadratic time. Finally, we discuss strategies for improving the lower bound.Supported by a grant from the Australia Research Council.     

On Construction of Optimal A2-Codes

§ 1.Ｉｎｔｒｏｄｕｃｔｉｏｎ　Ｔｈｅａｕｔｈｅｎｔｉｃａｔｉｏｎｃｏｄｅｓｗｉｔｈａｒｂｉｔｒａｔｉｏｎ (Ａ2 ｃｏｄｅｓ)ａｒｅｉｎｔｒｏｄｕｃｅｄｂｙＳｉｍｍｏｎｓ[1]ａｎｄｓｔｕｄｉｅｄｉｎｍａｎｙｐａｐｅｒｓ (ｆｏｒｅｘａｍｐｌｅ ,[1— 8] ) .Ｏｎｅｏｆｔｈｅｍｏｓｔｉｍｐｏｒｔａｎｔｐｒｏｂｌｅｍｓｉｎｔｈｅｓｔｕｄｙｏｆａｕｔｈｅｎｔｉｃａｔｉｏｎｃｏｄｅｓｉｓｔｏｆｉｎｄｌｏｗｅｒｂｏｕｎｄｓｏｎｃｈｅａｔｉｎｇｐｒｏｂａｂｉｌｉｔｉｅｓａｎｄｏｎｔｈｅｎｕｍｂｅｒｓｏｆｅｎｃｏｄｉ…     

A simple algorithm for tighter exact upper confidence bounds with rare attributes in finite universes

When attributes are rare and few or none are observed in the selected sample from a finite universe, sampling statisticians are increasingly being challenged to use whatever methods are available to declare with high probability or confidence that the universe is near or completely attribute-free. This is especially true when the attribute is undesirable. Approximations such as those based on normal theory are frequently inadequate with rare attributes. For simple random sampling without replacement, an appropriate probability distribution for statistical inference is the hypergeometric distribution. But even with the hypergeometric distribution, the investigator is limited from making claims of attribute-free with high confidence unless the sample size is quite large using nonrandomized techniques. For students in statistical theory, this short article seeks to revive the question of the relevance of randomized methods. When comparing methods for construction of confidence bounds in discrete settings, randomization methods are useful in fixing like confidence levels and hence facilitating the comparisons. Under simple random sampling, this article defines and presents a simple algorithm for the construction of exact “randomized” upper confidence bounds which permit one to possibly report tighter bounds than those exact bounds obtained using “nonrandomized” methods. A general theory for exact randomized confidence bounds is presented in Lehmann (1959, p. 81), but Lehmann's development requires more mathematical development than is required in this application. Not only is the development of these “randomized” bounds in this paper elementary, but their desirable properties and their link with the usual nonrandomized bounds are easy to see with the presented approach which leads to the same results as would be obtained using the method of Lehmann.     

Bounds and estimates on the effective properties for nonlinear composites

In this paper we derive lower bounds and upper bounds on the effective properties for nonlinear heterogeneous systems. The key result to obtain these bounds is to derive a variational principle, which generalizes the variational principle by P. Ponte Castaneda from 1992. In general, when the Ponte Castaneda variational principle is used one only gets either a lower or an upper bound depending on the growth conditions. In this paper we overcome this problem by using our new variational principle together with the bounds presented by Lukkassen, Persson and Wall in 1995. Moreover, we also present some examples where the bounds are so tight that they may be used as a good estimate of the effective behavior.     

A method for estimating interpolating polynomials

The question of obtaining a lower bound for some interpolating polynomials is considered. Under specific conditions it is proved that these bounds are sharp. As a corollary of the general theorem, under specific restrictions on the points of interpolation, lower bounds for Goncharov interpolation polynomials are obtained which coincide with known upper bounds.Translated from Matematicheskie Zametki, Vol. 17, No. 4, pp. 555–561, April, 1975.     

Error analysis for convex separable programs: Bounds on optimal and dual optimal solutions

Computable lower and upper bounds on the optimal and dual optimal solutions of a nonlinear, convex separable program are obtained from its piecewise linear approximation. They provide traditional error and sensitivity measures and are shown to be attainable for some problems. In addition, the bounds on the solution can be used to develop an efficient solution approach for such programs, and the dual bounds enable us to determine a subdivision interval which insures the objective function accuracy of a prespecified level. A generalization of the bounds to certain separable, but nonconvex, programs is given and some numerical examples are included.     

α次殆β型螺形映照齐次展开式的精细估计

从Loewner链的角度讨论C~n中单位球B~n上α次殆β型螺形映照齐次展开式的相关项的上界,并作为特殊情况得出β型螺形映照、星形映照和α次殆星形映照齐次展开式的相关项的上界估计,推广了螺形映照及星形映照齐次展开式的二次项系数的上界估计.     

Sharp upper and lower bounds for the Laplacian spectral radius and the spectral radius of graphs

In this paper, sharp upper bounds for the Laplacian spectral radius and the spectral radius of graphs are given, respectively. We show that some known bounds can be obtained from our bounds. For a bipartite graph G, we also present sharp lower bounds for the Laplacian spectral radius and the spectral radius, respectively.     

A Certain Class of Weighted Approximations for Integrable Functions and Applications

A certain class of weighted approximations, which extends the results of Masjed-Jamei [6] is introduced for integrable functions and some of upper bounds are obtained for the absolute value of the errors of such approximations in two L¹[a, b] and L^∞[a, b] spaces. As the main motivation for introducing the aforesaid class, it is shown that many new inequalities can be generated from the given error bounds. Some illustrative examples are presented in this sense. Moreover, by using the obtained error bounds, a nonstandard type of three-point weighted quadrature rules is introduced and its error bounds are computed.