首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 31 毫秒
1.
Anm×nmatrix =(ai, j), 1≤imand 1≤jn, is called atotally monotonematrix if for alli1, i2, j1, j2, satisfying 1≤i1<i2m, 1≤j1<j2n.[formula]We present an[formula]time algorithm to select thekth smallest item from anm×ntotally monotone matrix for anykmn. This is the first subquadratic algorithm for selecting an item from a totally monotone matrix. Our method also yields an algorithm of the same time complexity for ageneralized row-selection problemin monotone matrices. Given a setS={p1,…, pn} ofnpoints in convex position and a vectork={k1,…, kn}, we also present anO(n4/3logc n) algorithm to compute thekith nearest neighbor ofpifor everyin; herecis an appropriate constant. This algorithm is considerably faster than the one based on a row-selection algorithm for monotone matrices. If the points ofSare arbitrary, then thekith nearest neighbor ofpi, for allin, can be computed in timeO(n7/5 logc n), which also improves upon the previously best-known result.  相似文献   

2.
Olof Heden   《Discrete Mathematics》2009,309(21):6169-6180
A vector space partition of a finite dimensional vector space V=V(n,q) of dimension n over a finite field with q elements, is a collection of subspaces U1,U2,…,Ut with the property that every non zero vector of V is contained in exactly one of these subspaces. The tail of consists of the subspaces of least dimension d1 in , and the length n1 of the tail is the number of subspaces in the tail. Let d2 denote the second least dimension in .Two cases are considered: the integer qd2d1 does not divide respective divides n1. In the first case it is proved that if 2d1>d2 then n1qd1+1 and if 2d1d2 then either n1=(qd2−1)/(qd1−1) or n1>2qd2d1. These lower bounds are shown to be tight and the elements in the subspaces in tails of minimal length will constitute a subspace of V of dimension 2d1 respectively d2.In case qd2d1 divides n1 it is shown that if d2<2d1 then n1qd2qd1+qd2d1 and if 2d1d2 then n1qd2. The last bound is also shown to be tight.The results considerably improve earlier found lower bounds on the length of the tail.  相似文献   

3.
Martin Bokler   《Discrete Mathematics》2003,270(1-3):13-31
In this paper new lower bounds for the cardinality of minimal m-blocking sets are determined. Let r2(q) be the number such that q+r2(q)+1 is the cardinality of the smallest non-trivial line-blocking set in a plane of order q. If B is a minimal m-blocking set in PG(n,q) that contains at most qm+qm−1+…+q+1+r2(q)·(∑i=2mnm−1qi) points for an integer n′ satisfying mn′2m, then the dimension of B is at most n′. If the dimension of B is n′, then the following holds. The cardinality of B equals qm+qm−1+…+q+1+r2(q)(∑i=2mnm−1qi). For n′=m the set B is an m-dimensional subspace and for n′=m+1 the set B is a cone with an (m−2)-dimensional vertex over a non-trivial line-blocking set of cardinality q+r2(q)+1 in a plane skew to the vertex. This result is due to Heim (Mitt. Math. Semin. Giessen 226 (1996), 4–82). For n′>m+1 and q not a prime the number q is a square and for q16 the set B is a Baer cone. If q is odd and |B|<qm+qm−1+…+q+1+r2(q)(qm−1+qm−2), it follows from this result that the subspace generated by B has dimension at most m+1. Furthermore we prove that in this case, if , then B is an m-dimensional subspace or a cone with an (m−2)-dimensional vertex over a non-trivial line-blocking set of cardinality q+r2(q)+1 in a plane skew to the vertex. For q=p3h, p7 and q not a square we show this assertion for |B|qm+qm−1+…+q+1+q2/3·(qm−1+…+1).  相似文献   

4.
For given integers d,j≥2 and any positive integers n, distributions of n points in the d-dimensional unit cube [0,1]d are investigated, where the minimum volume of the convex hull determined by j of these n points is large. In particular, for fixed integers d,k≥2 the existence of a configuration of n points in [0,1]d is shown, such that, simultaneously for j=2,…,k, the volume of the convex hull of any j points among these n points is Ω(1/n(j−1)/(1+|dj+1|)). Moreover, a deterministic algorithm is given achieving this lower bound, provided that d+1≤jk.  相似文献   

5.
We show that with recently developed derandomization techniques, one can convert Clarkson's randomized algorithm for linear programming in fixed dimension into a linear-time deterministic algorithm. The constant of proportionality isdO(d), which is better than those for previously known algorithms. We show that the algorithm works in a fairly general abstract setting, which allows us to solve various other problems, e.g., computing the minimum-volume ellipsoid enclosing a set ofnpoints and finding the maximum volume ellipsoid in the intersection ofnhalfspaces.  相似文献   

6.
As proved by Hilbert, it is, in principle, possible to construct an arbitrarily close approximation in the Hausdorff metric to an arbitrary closed Jordan curve Γ in the complex plane {z} by lemniscates generated by polynomials P(z). In the present paper, we obtain quantitative upper bounds for the least deviations H n (Γ) (in this metric) from the curve Γ of the lemniscates generated by polynomials of a given degree n in terms of the moduli of continuity of the conformal mapping of the exterior of Γ onto the exterior of the unit circle, of the mapping inverse to it, and of the Green function with a pole at infinity for the exterior of Γ. For the case in which the curve Γ is analytic, we prove that H n (Γ) = O(q n ), 0 ≤ q = q(Γ) < 1, n → ∞.__________Translated from Matematicheskie Zametki, vol. 77, no. 6, 2005, pp. 861–876.Original Russian Text Copyright ©2005 by O. N. Kosukhin.  相似文献   

7.
Let (X, Y) be a random vector such that X is d-dimensional, Y is real valued, and θ(X) is the conditional αth quantile of Y given X, where α is a fixed number such that 0 < α < 1. Assume that θ is a smooth function with order of smoothness p > 0, and set r = (pm)/(2p + d), where m is a nonnegative integer smaller than p. Let T(θ) denote a derivative of θ of order m. It is proved that there exists estimate of T(θ), based on a set of i.i.d. observations (X1, Y1), …, (Xn, Yn), that achieves the optimal nonparametric rate of convergence nr in Lq-norms (1 ≤ q < ∞) restricted to compacts under appropriate regularity conditions. Further, it has been shown that there exists estimate of T(θ) that achieves the optimal rate (n/log n)r in L-norm restricted to compacts.  相似文献   

8.
Ito, Tanabe and Terwilliger recently introduced the notion of a tridiagonal pair. We apply their results to distance-regular graphs and obtain the following theorem.Theorem Let Γ denote a distance-regular graph with diameter D ≥  3. Suppose Γ is Q -polynomial with respect to the orderingE0 , E1, , EDof the primitive idempotents. For 0  ≤  i ≤  D, let midenote the multiplicity ofEi . Then (i)mi − 1 ≤ mi (1  ≤  i ≤  D / 2),(ii)mi  ≤ mD − i (0  ≤  i ≤ D  / 2).By proving the above theorem we resolve a conjecture of Dennis Stanton.  相似文献   

9.
Let p and q be two permutations over {1, 2,…, n}. We denote by m(p, q) the number of integers i, 1 ≤ in, such that p(i) = q(i). For each fixed permutation p, a query is a permutation q of the same size and the answer a(q) to this query is m(p, q). We investigate the problem of finding the minimum number of queries required to identify an unknown permutation p. A polynomial-time algorithm that identifies a permutation of size n by O(n · log2n) queries is presented. The lower bound of this problem is also considered. It is proved that the problem of determining the size of the search space created by a given set of queries and answers is #P-complete. Since this counting problem is essential for the analysis of the lower bound, a complete analysis of the lower bound appears infeasible. We conjecture, based on some preliminary analysis, that the lower bound is Ω(n · log2n).  相似文献   

10.
The n-widths of the unit ball Ap of the Hardy space Hp in Lq( −1, 1) are determined asymptotically. It is shown that for 1 ≤ q < p ≤∞ there exist constants k1 and k2 such that [formula]≤ dn(Ap, Lq(−1, 1)),dn(Ap, Lq(−1, 1)), δn(Ap, Lq(−1, 1))[formula]where dn, dn, and δn denote the Kolmogorov, Gel′fand and linear n-widths, respectively. This result is an improvement of estimates previously obtained by Burchard and Höllig and by the author.  相似文献   

11.
The flag geometry Γ=( ,  , I) of a finite projective plane Π of order s is the generalized hexagon of order (s, 1) obtained from Π by putting equal to the set of all flags of Π, by putting equal to the set of all points and lines of Π, and where I is the natural incidence relation (inverse containment), i.e., Γ is the dual of the double of Π in the sense of H. Van Maldeghem (1998, “Generalized Polygons,” Birkhäuser Verlag, Basel). Then we say that Γ is fully and weakly embedded in the finite projective space PG(dq) if Γ is a subgeometry of the natural point-line geometry associated with PG(dq), if s=q, if the set of points of Γ generates PG(dq), and if the set of points of Γ not opposite any given point of Γ does not generate PG(dq). In two earlier papers we have shown that the dimension d of the projective space belongs to {6, 7, 8}, that the projective plane Π is Desarguesian, and we have classified the full and weak embeddings of Γ (Γ as above) in the case that there are two opposite lines L, M of Γ with the property that the subspace ULM of PG(dq) generated by all lines of Γ meeting either L or M has dimension 6 (which is automatically satisfied if d=6). In the present paper, we partly handle the case d=7; more precisely, we consider for d=7 the case where for all pairs (LM) of opposite lines of Γ, the subspace ULM has dimension 7 and where there exist four lines concurrent with L contained in a 4-dimensional subspace of PG(7, q).  相似文献   

12.
For two subsets W and V of a Banach space X, let Kn(W, V, X) denote the relative Kolmogorov n-width of W relative to V defined by Kn (W, V, X) := inf sup Ln f∈W g∈V∩Ln inf ‖f-g‖x,where the infimum is taken over all n-dimensional linear subspaces Ln of X. Let W2(△r) denote the class of 2w-periodic functions f with d-variables satisfying ∫[-π,π]d |△rf(x)|2dx ≤ 1,while △r is the r-iterate of Laplace operator △. This article discusses the relative Kolmogorov n-width of W2(△r) relative to W2(△r) in Lq([-r, πr]d) (1 ≤ q ≤∞), and obtain its weak asymptotic result.  相似文献   

13.
A (p, q)-sigraph S is an ordered pair (G, s) where G = (V, E) is a (p, q)-graph and s is a function which assigns to each edge of G a positive or a negative sign. Let the sets E + and E consist of m positive and n negative edges of G, respectively, where m + n = q. Given positive integers k and d, S is said to be (k, d)-graceful if the vertices of G can be labeled with distinct integers from the set {0, 1, ..., k + (q – 1)d such that when each edge uv of G is assigned the product of its sign and the absolute difference of the integers assigned to u and v the edges in E + and E are labeled k, k + d, k + 2d, ..., k + (m – 1)d and –k, – (k + d), – (k + 2d), ..., – (k + (n – 1)d), respectively.In this paper, we report results of our preliminary investigation on the above new notion, which indeed generalises the well-known concept of (k, d)-graceful graphs due to B. D. Acharya and S. M. Hegde.  相似文献   

14.
We prove that there does not exist a [q4+q3q2−3q−1, 5, q4−2q2−2q+1]q code over the finite field for q≥ 5. Using this, we prove that there does not exist a [gq(5, d), 5, d]q code with q4 −2q2 −2q +1 ≤ dq4 −2q2q for q≥ 5, where gq(k,d) denotes the Griesmer bound.MSC 2000: 94B65, 94B05, 51E20, 05B25  相似文献   

15.
Let Γ denote a bipartite distance-regular graph with diameterD  ≥  4 and valency k ≥  3. Let θ 0  > θ 1  >  >  θD denote the eigenvalues of Γ and let E0, E1, , EDdenote the associated primitive idempotents. Fix s(1  ≤  s ≤  D −  1 ) and abbreviate E: =  Es. We say E is a tail whenever the entrywise product E   E is a linear combination of E0, E and at most one other primitive idempotent of Γ. Letqijσi + 1 h (0  ≤ h , i, j ≤  D) denote the Krein parameters of Γ and letΔ denote the undirected graph with vertices 0, 1, , D where two vertices i, j are adjacent whenever i ≠  =  j andqijσi + 1s  ≠  =  0. We show E is a tail if and only if one of (i)–(iii) holds: (i) Δ is a path; (ii) Δ has two connected components, each of which is a path; (iii) D =  6 and Δ has two connected components, one of which is a path on four vertices and the other of which is a clique on three vertices.  相似文献   

16.
Exact comparisons are made relating E|Y0|p, E|Yn−1|p, and E(maxjn−1 |Yj|p), valid for all martingales Y0,…,Yn−1, for each p ≥ 1. Specifically, for p > 1, the set of ordered triples {(x, y, z) : X = E|Y0|p, Y = E |Yn−1|p, and Z = E(maxjn−1 |Yj|p) for some martingale Y0,…,Yn−1} is precisely the set {(x, y, z) : 0≤xyz≤Ψn,p(x, y)}, where Ψn,p(x, y) = xψn,p(y/x) if x > 0, and = an−1,py if x = 0; here ψn,p is a specific recursively defined function. The result yields families of sharp inequalities, such as E(maxjn−1 |Yj|p) + ψn,p*(a) E |Y0|paE |Yn−1|p, valid for all martingales Y0,…,Yn−1, where ψn,p* is the concave conjugate function of ψn,p. Both the finite sequence and infinite sequence cases are developed. Proofs utilize moment theory, induction, conjugate function theory, and functional equation analysis.  相似文献   

17.
Primitive factorsq of 2 n –1,n odd, are either of the form 8m–1 or 8m+1. In the first case there exists a unique representation ofq in the quadratic forma 2–2b 2, (a, b)=1,a andb odd,b<[q/2], and in the latter a unique representation ofq in the quadratic formc 2+2 j d2, (c, d)=1,c andd odd,j even and 6. Thus the uniqueness ofq=a 2–2b 2 orc 2+2 j d2 exhibits a proof of the primality ofq.A program that determinesa, b, c, andd for anyq not exceeding 16 decimal digits is described, and as an example the 13-digit prime 4432676798593 (a primitive factor of 249–1) is uniquely represented by 13742732+214·124612.  相似文献   

18.
Comparisons are made between the expected gain of a prophet (an observer with complete foresight) and the maximal expected gain of a gambler (using only non-anticipating stopping times) observing a sequence of independent, uniformly bounded random variables where a non-negative fixed cost is charged for each observation. Sharp universal bounds are obtained under various restrictions on the cost and the length of the sequence. For example, it is shown for X1, X2, … independent, [0, 1]-valued random variables that for all c ≥ 0 and all n ≥ 1 that E(max1 ≤ jn(Xjjc)) − supt Tn E(Xttc) ≤ 1/e, where Tn is the collection of all stopping times t which are less than or equal to n almost surely.  相似文献   

19.
In bose&burton, Bose and Burton determined the smallest point sets of PG(d, q) that meet every subspace of PG(d, q) of a given dimension c. In this paper an equivalent result for quadrics of elliptic type is obtained. It states the folloing. For 0 c n - 1 the smallest point set of the elliptic quadric Q -(2n + 1, q) that meets every singular subspace of dimension c of Q -(2n + 1, q) has cardinality (q n+1 + q c )(q n-c - 1)/(q - 1). Furthermore, the point sets of the smallest cardinality are classified.  相似文献   

20.
Let n and k be positive integers. Let Cq be a cyclic group of order q. A cyclic difference packing (covering) array, or a CDPA(k, n; q) (CDCA(k, n; q)), is a k × n array (aij) with entries aij (0 ≤ ik−1, 0 ≤ jn−1) from Cq such that, for any two rows t and h (0 ≤ t < hk−1), every element of Cq occurs in the difference list at most (at least) once. When q is even, then nq−1 if a CDPA(k, n; q) with k ≥ 3 exists, and nq+1 if a CDCA(k, n; q) with k ≥ 3 exists. It is proved that a CDCA(4, q+1; q) exists for any even positive integers, and so does a CDPA(4, q−1; q) or a CDPA(4, q−2; q). The result is established, for the most part, by means of a result on cyclic difference matrices with one hole, which is of interest in its own right.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号