检索结果-内蒙古大学图书馆

SIAM JOURNAL ON COMPUTING 2004年第4期33卷 923-936页

作者： Devroye, L Morin, P Viola, A McGill Univ Sch Comp Sci Montreal PQ H3A 2K6 Canada Univ Republica Pedeciba Informat Montevideo Uruguay

We consider open addressing hashing and implement it by using the Robin Hood strategy;that is, in case of collision, the element that has traveled the farthest can stay in the slot. We hash similar to alphan elements into a table of size n where each probe is independent and uniformly distributed over the table, and alpha < 1 is a constant. Let M-n be the maximum search time for any of the elements in the table. We show that with probability tending to one, M-n is an element of[log(2) log n + sigma, log(2) log n + tau] for some constants sigma, tau depending upon alpha only. This is an exponential improvement over the maximum search time in case of the standard FCFS (first come first served) collision strategy and virtually matches the performance of multiple-choice hash methods.

关键词： open addressing hashing Robin Hood worst-case search time collision resolution probabilistic analysis of algorithms

来源：评论

学校读者我要写书评

暂无评论

A multivariate view of random bucket digital search trees

引用

JOURNAL OF algorithms-COGNITION INFORMATICS AND LOGIC 2002年第1期44卷 121-158页

作者： Hubalek, F Hwang, HK Lew, W Mahmoud, H Prodinger, H George Washington Univ Dept Stat Washington DC 20052 USA Vienna Univ Technol Inst Finanz & Versicherungsmath A-1040 Vienna Austria Acad Sinica Inst Stat Sci Taipei 115 Taiwan US Gen Accounting Off Ctr Technol & Engn Washington DC 20548 USA Univ Witwatersrand Sch Math ZA-2050 Johannesburg South Africa

We take a multivariate view of digital search trees by studying the number of nodes of different types that may coexist in a bucket digital search tree as it grows under an arbitrary memory management system. we obtain the mean of each type of node, as well as the entire covariance matrix between types, whereupon weak laws of large numbers follow from the orders of magnitude (the norming constants include oscillating functions). The result can be easily interpreted for practical systems like paging, heaps and UNIX's buddy system. The covariance results call for developing a Mellin convolution method, where convoluted numerical sequences are handled by convolutions of their Mellin transforms. Furthermore, we use a method of moments to show that the distribution is asymptotically normal. The method of proof is of some generality and is applicable to other parameters like path length and size in random tries and Patricia tries. (C) 2002 Elsevier Science (USA). All rights reserved.

关键词： random trees bucketing searching probabilistic analysis of algorithms Mellin transform Euler transform singularity analysis asymptotic normality

来源：评论

学校读者我要写书评

暂无评论

INTRODUCTION TO THE INTERFACE OF PROBABILITY AND algorithms

引用

STATISTICAL SCIENCE 1993年第1期8卷 3-9页

作者： ALDOUS, D STEELE, JM UNIV CALIF BERKELEY DEPT STATBERKELEYCA 94720 UNIV PENN WHARTON SCHDEPT STATPHILADELPHIAPA 19104

Probability and algorithms enjoy an almost boisterous interaction that has led to an active, extensive literature that touches fields as diverse as number theory and the design of computer hardware. This article offer... 详细信息

关键词： ASSIGNMENT PROBLEM probabilistic algorithms probabilistic analysis of algorithms RANDOMIZATION

来源：评论

学校读者我要写书评

暂无评论

Distances Between Pairs of Vertices and Vertical Profile in Conditioned Galton-Watson Trees

引用

RANDOM STRUCTURES & algorithms 2011年第4期38卷 381-395页

作者： Devroye, Luc Janson, Svante Uppsala Univ Dept Math SE-75106 Uppsala Sweden McGill Univ Sch Comp Sci Montreal PQ H3A 2K6 Canada

We consider a conditioned Galton-Watson tree and prove an estimate of the number of pairs of vertices with a given distance, or, equivalently, the number of paths of a given length. We give two proofs of this result, one probabilistic and the other using generating functions and singularity analysis. Moreover, the latter proof yields a more general estimate for generating functions, which is used to prove a conjecture by Bousquet-Melou and Janson (Bousquet-Melou and Janson, Ann Appl Probab 16 (2006) 1597-1632), saying that the vertical profile of a randomly labelled conditioned Galton-Watson tree converges in distribution, after suitable normalization, to the density of ISE (Integrated Superbrownian Excursion). (C) 2010 Wiley Periodicals, Inc. Random Struct. Alg., 38, 381-395, 2011

关键词： random Galton-Watson tree paths of given length vertical profile probabilistic analysis of algorithms branching process

来源：评论

学校读者我要写书评

暂无评论

Near-minimal spanning trees: A scaling exponent in probability models

引用

ANNALES DE L INSTITUT HENRI POINCARE-PROBABILITES ET STATISTIQUES 2008年第5期44卷 962-976页

作者： Aldous, David J. Bordenave, Charles Lelarge, Marc Univ Calif Berkeley Dept Stat Berkeley CA 94720 USA Ecole Normale Super Dept Informat F-75230 Paris 5 France INRIA ENS F-75230 Paris 5 France

We study the relation between the minimal spanning tree (MST) on many random points and the "near-minimal" tree which is optimal subject to the constraint that a proportion 3 of its edges must be different from those of the MST. Heuristics suggest that, regardless of details of the probability model. the ratio of lengths should scale as 1 + Theta (delta(2)). We prove this scaling result in the model of the lattice with random edge-lengths and in the Euclidean model.

关键词： Combinatorial optimization Continuum percolation Disordered lattice Local weak convergence Minimal spanning tree Poisson point process probabilistic analysis of algorithms Random geometric graph

来源：评论

学校读者我要写书评

暂无评论

On average case complexity of SAT for symmetric distribution

引用

Journal of Logic and Computation 1995年第1期5卷 71-71页

作者： Makowsky, J. Sharell, A. Faculty of Computer Science Technion-Israel Institute of Technology Haifa Israel Laboratoire de Recherche en Informatique Université 91405 Orsay Paris-Sud France

We investigate in this paper ‘natural’ distributions for the satisfiability problem (SAT) of prepositional logic, using concepts previously introduced by to study the average-case complexity of NP-complete problems. Gurevich showed that a problem with aflatdistribution is not DistNP complete (for deterministic reductions), unless DEXPTIme ≠ NEXPTlme. We express the known results concerningfixed sizeandfixed densitydistributions for CNF in the framework of average-case complexity and show that all these distributions are flat. We introduce the family of symmetric distributions, which generalizes those mentioned before, and show that bounded symmetric distributions on ordered tuples of clauses (CNFTupIes) and onk-CNF (sets ofk-literal-clauses), are flat. This eliminates all these distributions as candidates for ‘provably hard’ (i.e. DistNP complete) distributions for SAT, if one considers only deterministic reductions. Given the (presumed) naturalness and generality of these distributions, this result supports evidence that (at least polynomial-time, no-error) randomized reductions are appropriate in average-case complexity. We also observe, that there are non-flat distributions for which SAT is polynomial on the average, but that this is due to the particular choice of the size functions. Finally, Chváal and Szemerédi have shown that for certain fixed size distributions (which are also flat) resolution is exponential for almost all instances. We use this to show that every resolution algorithm will need at least exp(nα) (for any 0 ≤ α ≤ 1) time on the average. In other words, resolution-based algorithms will not establish that SAT, with these distributions, is in AverP.

关键词： Average case complexity probabilistic analysis of algorithms Resolution Satisfiability problem

来源：评论

学校读者我要写书评

暂无评论

The ζ(2) limit in the random assignment problem

引用

RANDOM STRUCTURES & algorithms 2001年第4期18卷 381-418页

作者： Aldous, DJ Univ Calif Berkeley Dept Stat Berkeley CA 94720 USA

The random assignment (or bipartite matching) problem asks about A, min(pi) Sigma (n)(i=1) c(i, pi (i)), where (c(i, j)) is a n x n matrix with i.i.d. entries, say with exponential(1) distribution, and the minimum is over permutations pi. Mezard and Parisi (1987) used the replica method from statistical physics to argue nonrigorously that EA(n) --> zeta (2) = pi (2)/6. Aldous (1992) identified the limit in terms of a matching problem on a limit infinite tree. Herl we construct the optimal matching on the infinite tree. This yields a rigorous proof of the zeta (2) limit and of the conjectured limit distribution od edge-costs and their rank-orders in the optimal matching. It also yields the asymptotic essential uniqueness property: every almost-optimal matching coincides with the optimal matching except on a small proportion of edges. (C) 2001 John Wiley & Sons, Inc.

关键词： assignment problem bipartite matching cavity method combinatorial optimization distributional identity infinite tree probabilistic analysis of algorithms probabilistic combinatorics random matrix replica method replica symmetry

来源：评论

学校读者我要写书评

暂无评论

Selection by rank in K-dimensional binary search trees

引用

RANDOM STRUCTURES & algorithms 2014年第1期45卷 14-37页

作者： Duch, Amalia Jimenez, Rosa M. Martinez, Conrado Univ Politecn Cataluna Dept Llenguatges & Sistemes Informat E-08034 Barcelona Spain

In this work we show how to augment general purpose multidimensional data structures, such as K-d trees, to efficiently support search by rank (that is, to locate the i-th smallest element along the j-th coordinate, for given i and j) and to find the rank of a given item along a given coordinate. To do so, we introduce two simple, practical and very flexible algorithms - Select-by-Rank and Find-Rank - with very little overhead. Both algorithms can be easily implemented and adapted to several spatial indexes, although their analysis is far from trivial. We are able to show that for random K-d trees of size n the expected number of nodes visited by Find-Rank is Pn,i=(n1-1/K) for i=o(n) or i=n-o(n), and Pn,i=fK(i/n)center dot n+o(n) for i=xn+o(n) (with 0algorithms. As a byproduct of the analysis of our algorithms, but no less important, we give the average-case analysis of a partial match search in random K-d trees when the query is not random. (c) 2012 Wiley Periodicals, Inc. Random Struct. Alg., 45, 14-37, 2014

关键词： Multidimensional data structures selection K-dimensional search trees partial match probabilistic analysis of algorithms

来源：评论

学校读者我要写书评

暂无评论

ON THE POWER OF ADAPTIVE INFORMATION FOR FUNCTIONS WITH SINGULARITIES

引用

MATHEMATICS OF COMPUTATION 1992年第197期58卷 285-304页

作者： WASILKOWSKI, GW GAO, F UNIV BRITISH COLUMBIA DEPT COMP SCIVANCOUVER V6T 1W5BCCANADA

We study from a probabilistic viewpoint the problem of locating singularities of functions using function evaluations. We show that, under the assumption of a Wiener-like probability distribution on the class of singular functions, an adaptive algorithm can locate a singular point accurately with only a small probability of failure. As an application, we show that an integration algorithm that adaptively locates a singular point is probabilistically superior to nonadaptive algorithms.

关键词： PIECEWISE REGULAR FUNCTIONS APPROXIMATING DETECTING SINGULAR POINTS probabilistic analysis of algorithms ADAPTIVE (SEQUENTIAL) algorithms ADAPTIVE QUADRATURES

来源：评论

学校读者我要写书评

暂无评论

Recursive functions on conditional Galton-Watson trees

引用

RANDOM STRUCTURES & algorithms 2020年第2期57卷 304-316页

作者： Broutin, Nicolas Devroye, Luc Fraiman, Nicolas Sorbonne Univ Campus Pierre & Marie CurieCase Courrier 158 4 F-75252 Paris 05 France McGill Univ Sch Comp Sci Montreal PQ Canada Univ N Carolina Dept Stat & Operat Res Chapel Hill NC 27515 USA

A recursive function on a tree is a function in which each leaf has a given value, and each internal node has a value equal to a function of the number of children, the values of the children, and possibly an explicitly specified random elementU. The value of the root is the key quantity of interest in general. In this study, all node values and function values are in a finite setS. In this note, we describe the limit behavior when the leaf values are drawn independently from a fixed distribution onS, and the treeT(n)is a random Galton-Watson tree of sizen.

关键词： branching process probabilistic analysis of algorithms random Galton-Watson tree recursive functions

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：