共查询到20条相似文献,搜索用时 31 毫秒
1.
Georgios Psarrakos 《Insurance: Mathematics and Economics》2008,43(2):197-202
We obtain upper and lower bounds for the tail of the deficit at ruin in the renewal risk model, which are (i) applicable generally; and (ii) based on reliability classifications. We also derive two-side bounds, in the general case where a function satisfies a defective renewal equation, and we apply them to the renewal model, using the function Λu introduced by [Psarrakos, G., Politis, K., 2007. A generalisation of the Lundberg condition in the Sparre Andersen model and some applications (submitted for publication)]. Finally, we construct an upper bound for the integrated function and an asymptotic result when the adjustment coefficient exists. 相似文献
2.
We prove that any pair of bivariate trinomials has at most five isolated roots
in the positive quadrant. The best previous upper bounds independent of the polynomial
degrees were much larger, e.g., 248832 (for just the non-degenerate roots) via a famous
general result of Khovanski. Our bound is sharp, allows real exponents, allows degeneracies,
and extends to certain systems of n-variate fewnomials, giving improvements over earlier
bounds by a factor exponential in the number of monomials. We also derive analogous
sharpened bounds on the number of connected components of the real zero set of a single
n-variate m-nomial. 相似文献
3.
In this paper we consider numerical integration of smooth functions lying in a particular reproducing kernel Hilbert space. We show that the worst-case error of numerical integration in this space converges at the optimal rate, up to some power of a log?N factor. A similar result is shown for the mean square worst-case error, where the bound for the latter is always better than the bound for the square worst-case error. Finally, bounds for integration errors of functions lying in the reproducing kernel Hilbert space are given. The paper concludes by illustrating the theory with numerical results. 相似文献
4.
Lenny Fukshansky 《Journal of Combinatorial Theory, Series A》2011,118(2):690-701
We find sharp absolute constants C1 and C2 with the following property: every well-rounded lattice of rank 3 in a Euclidean space has a minimal basis so that the solid angle spanned by these basis vectors lies in the interval [C1,C2]. In fact, we show that these absolute bounds hold for a larger class of lattices than just well-rounded, and the upper bound holds for all. We state a technical condition on the lattice that may prevent it from satisfying the absolute lower bound on the solid angle, in which case we derive a lower bound in terms of the ratios of successive minima of the lattice. We use this result to show that among all spherical triangles on the unit sphere in RN with vertices on the minimal vectors of a lattice, the smallest possible area is achieved by a configuration of minimal vectors of the (normalized) face centered cubic lattice in R3. Such spherical configurations come up in connection with the kissing number problem. 相似文献
5.
J. Erickson 《Discrete and Computational Geometry》1996,16(4):389-418
We establish new lower bounds on the complexity of the following basic geometric problem, attributed to John Hopcroft: Given a set ofn points andm hyperplanes in $\mathbb{R}^d $ , is any point contained in any hyperplane? We define a general class ofpartitioning algorithms, and show that in the worst case, for allm andn, any such algorithm requires time Ω(n logm + n 2/3m2/3 + m logn) in two dimensions, or Ω(n logm + n 5/6m1/2 + n1/2m5/6 + m logn) in three or more dimensions. We obtain slightly higher bounds for the counting version of Hopcroft's problem in four or more dimensions. Our planar lower bound is within a factor of 2O(log*(n+m)) of the best known upper bound, due to Matou?ek. Previously, the best known lower bound, in any dimension, was Ω(n logm + m logn). We develop our lower bounds in two stages. First we define a combinatorial representation of the relative order type of a set of points and hyperplanes, called amonochromatic cover, and derive lower bounds on its size in the worst case. We then show that the running time of any partitioning algorithm is bounded below by the size of some monochromatic cover. As a related result, using a straightforward adversary argument, we derive aquadratic lower bound on the complexity of Hopcroft's problem in a surprisingly powerful decision tree model of computation. 相似文献
6.
We use entropy numbers in combination with the polynomial method to derive a new general lower bound for the nth minimal error in the quantum setting of information-based complexity. As an application, we improve some lower bounds on quantum approximation of embeddings between finite dimensional Lp spaces and of Sobolev embeddings. 相似文献
7.
《Journal of Computational and Applied Mathematics》1996,75(2):249-258
It is shown here that the first three terms of the asymptotic expansion of jvk, k = 1, 2, 3, provide an upper bound for jvk in 0 < v ⩽ 10, hence a “best possible” upper bound. Lang and Wong have shown that this is true also for 10 < v < ∞ when k = 1 and 2, so that these “best possible” upper bounds hold in the entire interval 0 < v < ∞ in these cases. We include supplementary comments on lower bounds in 0 ⩽ v ⩽ 10. 相似文献
8.
In the present paper we continue the work begun by Sauer, Perles, Shelah and Anstee on forbidden configurations of 0–1 matrices. We give asymptotically exact bounds for all possible 2 × l forbidden submatrices and almost all 3 × l ones. These bounds are improvements of the general bounds, or else new constructions show that the general bound is best possible. It is interesting to note that up to the present state of our knowledge every forbidden configuration results in polynomial asymptotic. 相似文献
9.
Ulrich Kohlenbach 《Journal of Mathematical Analysis and Applications》2003,279(2):531-544
In Numer. Funct. Anal. Optim. 22 (2001) 641-656, we obtained an effective quantitative analysis of a theorem due to Borwein, Reich, and Shafrir on the asymptotic behavior of general Krasnoselski-Mann iterations for nonexpansive self-mappings of convex sets C in arbitrary normed spaces. We used this result to obtain a new strong uniform version of Ishikawa's theorem for bounded C. In this paper we give a qualitative improvement of our result in the unbounded case and prove the uniformity result for the bounded case under the weaker assumption that C contains a point x whose Krasnoselski-Mann iteration (xk) is bounded. We also consider more general iterations for which asymptotic regularity is known only for uniformly convex spaces (Groetsch). We give uniform effective bounds for (an extension of) Groetsch's theorem which generalize previous results by Kirk, Martinez-Yanez, and the author. 相似文献
10.
Ji?í Fiala 《Discrete Applied Mathematics》2010,158(7):771-368
Packing coloring is a partitioning of the vertex set of a graph with the property that vertices in the i-th class have pairwise distance greater than i. The main result of this paper is a solution of an open problem of Goddard et al. showing that the decision whether a tree allows a packing coloring with at most k classes is NP-complete.We further discuss specific cases when this problem allows an efficient algorithm. Namely, we show that it is decideable in polynomial time for graphs of bounded treewidth and diameter, and fixed parameter tractable for chordal graphs.We accompany these results by several observations on a closely related variant of the packing coloring problem, where the lower bounds on the distances between vertices inside color classes are determined by an infinite nondecreasing sequence of bounded integers. 相似文献
11.
This paper examines worst-case evaluation bounds for finding weak minimizers in unconstrained optimization. For the cubic regularization algorithm, Nesterov and Polyak (2006) [15] and Cartis et al. (2010) [3] show that at most O(?−3) iterations may have to be performed for finding an iterate which is within ? of satisfying second-order optimality conditions. We first show that this bound can be derived for a version of the algorithm, which only uses one-dimensional global optimization of the cubic model and that it is sharp. We next consider the standard trust-region method and show that a bound of the same type may also be derived for this method, and that it is also sharp in some cases. We conclude by showing that a comparison of the bounds on the worst-case behaviour of the cubic regularization and trust-region algorithms favours the first of these methods. 相似文献
12.
We obtain upper bounds for character sums modulo a composite number over sets of numbers with missing digits in a number system. We derive results on the solvability of congruences of the form x 1 ? x t ≡ λ (mod m) in the numbers with missing digits and also asymptotic formulas for the number of solutions. 相似文献
13.
J.M. Varah 《Linear algebra and its applications》1975,11(1):3-5
For a matrix A which is diagonally dominant both by rows and by columns, we give bounds for 6A-161 and 6A-16∞, which then can be used to give a lower bound for the smallest singular value. We also show that these bounds can be attained, and show how the result can be extended to block matrices. 相似文献
14.
We derive in closed form distribution free lower bounds and optimal subreplicating strategies for spread options in a one-period static arbitrage setting. In the case of a continuum of strikes, we complement the optimal lower bound for spread options obtained in [Rapuch, G., Roncalli, T., 2002. Pricing multiasset options and credit derivatives with copula, Credit Lyonnais, Working Papers] by describing its corresponding subreplicating strategy. This result is explored numerically in a Black-Scholes and in a CEV setting. In the case of discrete strikes, we solve in closed form the optimization problem in which, for each asset S1 and S2, forward prices and the price of one option are used as constraints on the marginal distributions of each asset. We provide a partial solution in the case where the marginal distributions are constrained by two strikes per asset. Numerical results on real NYMEX (New York Mercantile Exchange) crack spread option data show that the one discrete lower bound can be far and also very close to the traded price. In addition, the one strike closed form solution is very close to the two strike. 相似文献
15.
G. C. Bell A. N. Dranishnikov 《Transactions of the American Mathematical Society》2006,358(11):4749-4764
We prove an asymptotic analog of the classical Hurewicz theorem on mappings that lower dimension. This theorem allows us to find sharp upper bound estimates for the asymptotic dimension of groups acting on finite-dimensional metric spaces and allows us to prove a useful extension theorem for asymptotic dimension. As applications we find upper bound estimates for the asymptotic dimension of nilpotent and polycyclic groups in terms of their Hirsch length. We are also able to improve the known upper bounds on the asymptotic dimension of fundamental groups of complexes of groups, amalgamated free products and the hyperbolization of metric spaces possessing the Higson property.
16.
Approximation algorithms for single machine scheduling with one unavailability period 总被引:2,自引:0,他引:2
In this paper, we investigate the single machine scheduling problem with release dates and tails and a planned unavailability
time period. We show that the problem admits a fully polynomial-time approximation scheme when the tails are equal. We derive
an approximation algorithm for the general case and we show that the worst-case bound of the sequence yielded by Schrage’s
algorithm is equal to 2 and that this bound is tight. Some consequences of this result are also presented.
相似文献
17.
The bin packing problem is one of the classical NP-hard optimization problems. In this paper, we present a simple generic
approach for obtaining new fast lower bounds, based on dual feasible functions. Worst-case analysis as well as computational
results show that one of our classes clearly outperforms the previous best “economical” lower bound for the bin packing problem
by Martello and Toth, which can be understood as a special case. In particular, we prove an asymptotic worst-case performance
of 3/4 for a bound that can be computed in linear time for items sorted by size. In addition, our approach provides a general
framework for establishing new bounds.
Received: August 11, 1998 / Accepted: February 1, 2001?Published online September 17, 2001 相似文献
18.
Frances Y. Kuo Grzegorz W. Wasilkowski Henryk Woźniakowski 《Constructive Approximation》2009,30(3):475-493
We approximate d-variate functions from weighted Korobov spaces with the error of approximation defined in the L ∞ sense. We study lattice algorithms and consider the worst-case setting in which the error is defined by its worst-case behavior over the unit ball of the space of functions. A lattice algorithm is specified by a generating (integer) vector. We propose three choices of such vectors, each corresponding to a different search criterion in the component-by-component construction. We present worst-case error bounds that go to zero polynomially with n ?1, where n is the number of function values used by the lattice algorithm. Under some assumptions on the weights of the function space, the worst-case error bounds are also polynomial in d, in which case we have (polynomial) tractability, or even independent of d, in which case we have strong (polynomial) tractability. We discuss the exponents of n ?1 and stress that we do not know if these exponents can be improved. 相似文献
19.
We study upper and lower bounds for the lowest eigenvalueλ of the Laplace operator on a spherical capC θ inm-dimensional space (m ≥ 3). We prove that these bounds are sharp by finding asymptotic expressions forλ asθ → π and asθ → 0. 相似文献
20.
Úlfar F. Stefánsson 《Constructive Approximation》2010,32(2):193-220
We provide a representation for the Müntz orthogonal polynomials as a real integral. This allows us to establish a general result on their asymptotic behavior within the interval of orthogonality. This is the first time that such asymptotics have been obtained for general Müntz exponents {λ n }. We consider some special cases, particularly when the exponents satisfy the asymptotic relation $\lim_{n\rightarrow\infty}\frac{n}{\lambda_n}=\rho $ for some constant ρ>0. 相似文献