共查询到20条相似文献,搜索用时 78 毫秒
1.
Ursula Hamenstädt 《Journal of Geometric Analysis》2004,14(2):281-290
Let M be a complete geometrically finite manifold of bounded negative curvature, infinite volume, and dimension at least 3.We give both a lower bound for the bottom of the spectrum of M and an upper bound for the number of the small eigenvalues
of M. These bounds only depend on the dimension, curvature bounds and the volume of the oneneighborhood of the convex core. 相似文献
2.
Jia-zu Zhou 《中国科学A辑(英文版)》2007,50(3):325-333
Let ∑ be a convex hypersurface in the Euclidean space R4 with mean curvature H. We obtain a geometric lower bound for the Willmore functional f∑ H2dσ. This bound is an invariant involving the area of ∑, the volume and Minkowski quermassintegrals of the convex body that ∑bounds. We also obtain a sufficient condition for a convex body to contain another in the Euclidean space R4. 相似文献
3.
We address a class of particularly hard-to-solve combinatorial optimization problems, namely that of multicommodity network optimization when the link cost functions are discontinuous step increasing. Unlike usual approaches consisting in the development of relaxations for such problems (in an equivalent form of a large scale mixed integer linear programming problem) in order to derive lower bounds, our d.c.(difference of convex functions) approach deals with the original continuous version and provides upper bounds. More precisely we approximate step increasing functions as closely as desired by differences of polyhedral convex functions and then apply DCA (difference of convex function algorithm) to the resulting approximate polyhedral d.c. programs. Preliminary computational experiments are presented on a series of test problems with structures similar to those encountered in telecommunication networks. They show that the d.c. approach and DCA provide feasible multicommodity flows x
* such that the relative differences between upper bounds (computed by DCA) and simple lower bounds r:=(f(x*)-LB)/{f(x*)} lies in the range [4.2 %, 16.5 %] with an average of 11.5 %, where f is the cost function of the problem and LB is a lower bound obtained by solving the linearized program (that is built from the original problem by replacing step increasing cost functions with simple affine minorizations). It seems that for the first time so good upper bounds have been obtained. 相似文献
4.
H. Moulin 《International Journal of Game Theory》1990,19(2):219-232
In a TU cooperative game with populationN, a monotonic core allocation allocates each surplusv (S) among the agents of coalitionS in such a way that agenti's share never decreases when the coalition to which he belongs expands.We investigate the property of largeness (Sharkey [1982]) for monotonic cores. We show the following result. Given a convex TU game and an upper bound on each agent' share in each coalition containing him, if the upper bound depends only upon the size of the coalition and varies monotonically as the size increases, then there exists a monotonic core allocation meeting this system of upper bounds. We apply this result to the provision of a public good problem. 相似文献
5.
Jochen W. Schmidt 《BIT Numerical Mathematics》1991,31(2):328-340
The problem of convex interval interpolation with cubicC
1-splines has an infinite number of solutions, if it is solvable at all. For selecting one of the solutions a regularized mean curvature is minimized. The arising finite dimensional constrained program is solved numerically by means of a dualization approach.Dedicated to Professor Julius Albrecht on the occasion of his 65th birthday. 相似文献
6.
The relative generalized Hamming weight (RGHW) of a linear code C and a subcode C 1 is an extension of generalized Hamming weight. The concept was firstly used to protect messages from an adversary in the wiretap channel of type II with illegitimate parties. It was also applied to the wiretap network II for secrecy control of network coding and to trellis-based decoding algorithms for complexity estimation. For RGHW, bounds and code constructions are two related issues. Upper bounds on RGHW show the possible optimality for the applications, and code constructions meeting upper bounds are for designing optimal schemes. In this article, we show indirect and direct code constructions for known upper bounds on RGHW. When upper bounds are not tight or constructions are hard to find, we provide two asymptotically equivalent existence bounds about good code pairs for designing suboptimal schemes. Particularly, most code pairs (C, C 1) are good when the length n of C is sufficiently large, the dimension k of C is proportional to n and other parameters are fixed. Moreover, the first existence bound yields an implicit lower bound on RGHW, and the asymptotic form of this existence bound generalizes the usual asymptotic Gilbert–Varshamov bound. 相似文献
7.
We study some systems of polynomials whose support lies in the convex hull of a circuit, giving a sharp upper bound for their
numbers of real solutions. This upper bound is non-trivial in that it is smaller than either the Kouchnirenko or the Khovanskii
bounds for these systems. When the support is exactly a circuit whose affine span is ℤn, this bound is 2n+1, while the Khovanskii bound is exponential in n2. The bound 2n+1 can be attained only for non-degenerate circuits. Our methods involve a mixture of combinatorics, geometry, and arithmetic.
Part of work done at MSRI was supported by NSF grant DMS-9810361.
Work of Sottile is supported by the Clay Mathematical Institute.
Sottile and Bihan were supported in part by NSF CAREER grant DMS-0134860.
Bertrand is supported by the European research network IHP-RAAG contract HPRN-CT-2001-00271. 相似文献
8.
We establish a C2 a priori estimate for convex hypersurfaces whose principal curvatures κ=(κ1,…, κn) satisfy σk(κ(X))=f(X,ν(X)), the Weingarten curvature equation. We also obtain such an estimate for admissible 2‐convex hypersurfaces in the case k=2. Our estimates resolve a longstanding problem in geometric fully nonlinear elliptic equations.© 2015 Wiley Periodicals, Inc. 相似文献
9.
Tomasz Radzik 《Mathematical Programming》1996,78(1):43-58
In this paper we consider an optimization version of the multicommodity flow problem which is known as the maximum concurrent
flow problem. We show that an approximate solution to this problem can be computed deterministically using O(k(ε
−2 + logk) logn) 1-commodity minimum-cost flow computations, wherek is the number of commodities,n is the number of nodes, andε is the desired precision. We obtain this bound by proving that in the randomized algorithm developed by Leighton et al. (1995)
the random selection of commodities can be replaced by the deterministic round-robin without increasing the total running
time. Our bound significantly improves the previously known deterministic upper bounds and matches the best known randomized
upper bound for the approximation concurrent flow problem.
A preliminary version of this paper appeared inProceedings of the 6th ACM-SIAM Symposium on Discrete Algorithms, San Francisco CA, 1995, pp. 486–492. 相似文献
10.
A. L. Yampol'skií 《Journal of Mathematical Sciences》1990,48(1):108-117
We study the sectional curvaturesK of the Sasaki metric of tangent sphere bundles over spaces of constant curvatureK(T
1(M
n, K)). We give precise bounds on the variation of the Ricci curvature and a bound on the scalar curvature ofT
1 (M
n, K) that is uniform onK. In an appendix we calculate and give lower bounds for the lengths of closed geodesics onT
1
S
n. titles.Translated from Ukrainskií Geometricheskií Sbornik, Issue 28, 1985, pp. 132–145. 相似文献
11.
Let ℬ be a set ofn arbitrary (possibly intersecting) convex obstacles in ℝ
d
. It is shown that any two points which can be connected by a path avoiding the obstacles can also be connected by a path
consisting ofO(n
(d−1)[d/2+1]) segments. The bound cannot be improved below Ω(n
d
); thus, in ℝ3, the answer is betweenn
3 andn
4. For open disjoint convex obstacles, a Θ(n) bound is proved. By a well-known reduction, the general case result also upper bounds the complexity for a translational
motion of an arbitrary convex robot among convex obstacles. Asymptotically tight bounds and efficient algorithms are given
in the planar case.
This research was supported by The Netherlands' Organization for Scientific Research (NWO) and partially by the ESPRIT III
Basic Research Action 6546 (PROMotion). J. M. acknowledges support by a Humboldt Research Fellowship. Part of this research
was done while he visited Utrecht University. 相似文献
12.
Jong-Gug Yun 《Archiv der Mathematik》2005,85(2):167-174
In this paper, we give an upper bound on the growth of π1(M) for a class of manifolds with integral Ricci curvature bounds. This generalizes the main theorem of [8] to the case where the negative part of Ricci curvature is small in an averaged L1- sense.Received: 19 July 2004 相似文献
13.
Jia-zu Zhou 《中国科学 数学(英文版)》2007,50(3):325-333
Let Σ be a convex hypersurface in the Euclidean space R 4 with mean curvature H. We obtain a geometric lower bound for the Willmore functional ∫Σ H 2 dσ. This bound is an invariant involving the area of Σ, the volume and Minkowski quermassintegrals of the convex body that Σ bounds. We also obtain a sufficient condition for a convex body to contain another in the Euclidean space R 4. 相似文献
14.
Wiesława T. Obuchowska 《Journal of Global Optimization》2010,46(3):423-433
In this paper we investigate certain aspects of infeasibility in convex integer programs, where the constraint functions are
defined either as a composition of a convex increasing function with a convex integer valued function of n variables or the sum of similar functions. In particular we are concerned with the problem of an upper bound for the minimal
cardinality of the irreducible infeasible subset of constraints defining the model. We prove that for the considered class
of functions, every infeasible system of inequality constraints in the convex integer program contains an inconsistent subsystem
of cardinality not greater than 2
n
, this way generalizing the well known theorem of Scarf and Bell for linear systems. The latter result allows us to demonstrate
that if the considered convex integer problem is bounded below, then there exists a subset of at most 2
n
−1 constraints in the system, such that the minimum of the objective function subject to the inequalities in the reduced subsystem,
equals to the minimum of the objective function over the entire system of constraints. 相似文献
15.
Zoran H. Peri Jelena R. Nikoli Marko D. Petkovi 《Mathematical Methods in the Applied Sciences》2019,42(6):1786-1794
In this paper, we propose a novel class of parametric bounds on the Q‐function, which are lower bounds for 1 ≤ a < 3 and x > xt = (a (a‐1) / (3‐a))1/2, and upper bound for a = 3. We prove that the lower and upper bounds on the Q‐function can have the same analytical form that is asymptotically equal, which is a unique feature of our class of tight bounds. For the novel class of bounds and for each particular bound from this class, we derive the beneficial closed‐form expression for the upper bound on the relative error. By comparing the bound tightness for moderate and large argument values not only numerically, but also analytically, we demonstrate that our bounds are tighter compared with the previously reported bounds of similar analytical form complexity. 相似文献
16.
The problem of interpolation by a convex curve to the vertices of a convex polygon is considered. A natural 1-parameter family ofC
algebraic curves solving this problem is presented. This is extended to a solution, of a general Hermite-type problem, in, which the curve also interpolates to one or two prescribedtangents at any desired vertices of the polygon. The construction of these curves is a generalization of well known methods for generatingconic sections. Several properties of this family of algebraic curves are discussed. In addition, the method is generalized to convexC
interpolation of strictly convex data sets inR
3 by algebraicsurfaces. 相似文献
17.
We prove that sets of positive reach in Riemannian manifolds and more generally, almost convex subsets in spaces with an upper curvature bound have an upper curvature bound with respect to the inner metric.Mathematics Subject Classification (2000): 53C20 相似文献
18.
We investigate universal bounds on spherical codes and spherical
designs that could be obtained using Delsartes
linear programming methods. We
give a lower estimate for the LP upper bound on codes, and an
upper estimate for the LP lower bound on designs.
Specifically, when the distance of the code is fixed and the
dimension goes to infinity, the LP upper bound on codes is at least as
large as the average of the best known upper and lower bounds.
When the dimension n of the design is fixed, and the strength k
goes to infinity, the LP bound on designs turns out,
in conjunction with known lower bounds, to be proportional to kn-1. 相似文献
19.
Asma Hassannezhad 《Journal of Functional Analysis》2011,261(12):3419-3436
In this paper, we find upper bounds for the eigenvalues of the Laplacian in the conformal class of a compact Riemannian manifold (M,g). These upper bounds depend only on the dimension and a conformal invariant that we call “min-conformal volume”. Asymptotically, these bounds are consistent with the Weyl law and improve previous results by Korevaar and Yang and Yau. The proof relies on the construction of a suitable family of disjoint domains providing supports for a family of test functions. This method is interesting for itself and powerful. As a further application of the method we obtain an upper bound for the eigenvalues of the Steklov problem in a domain with C1 boundary in a complete Riemannian manifold in terms of the isoperimetric ratio of the domain and the conformal invariant that we introduce. 相似文献
20.
We obtain asymptotic equalities for upper bounds of approximations of functions from the class C
β,∞ψ by Poisson integrals in the metric of the space C. 相似文献