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

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

来源：评论

学校读者我要写书评

暂无评论

probabilistic analysis of unit-demand vehicle routeing problems

引用

JOURNAL OF APPLIED PROBABILITY 2007年第1期44卷 259-278页

作者： Bompadre, Agustin Dror, Moshe Orlin, James B. MIT Alfred P Sloan Sch Management Cambridge MA 02142 USA

We analyze the unit-demand Euclidean vehicle routeing problem, where n customers are modeled as independent, identically distributed uniform points and have unit demand. We show new lower bounds on the optimal cost for the metric vehicle routeing problem and analyze them in this setting. We prove that there exists a constant (c) over cap > 0 such that the iterated tour partitioning heuristic given by Haimovich and Rinnooy Kan (1985) is a (2 - (c) over cap)-approximation algorithm with probability arbitrarily close to I as the number of customers goes to infinity. It has been a longstanding open problem as to whether one can improve upon the factor of 2 given by Haimovich and Rinnooy Kan. We also generalize this, and previous results, to the multidepot case.

关键词： vehicle routeing problem heuristic probabilistic analysis of algorithms

来源：评论

学校读者我要写书评

暂无评论

Exponential tail bounds for max-recursive sequences

引用

ELECTRONIC COMMUNICATIONS IN PROBABILITY 2006年第none期11卷 266-277页

作者： Rueschendorf, Ludger Schopp, Eva-Maria Univ Freiburg Dept Math Stochast D-79104 Freiburg Germany

Exponential tail bounds are derived for solutions of max-recursive equations and for max-recursive random sequences, which typically arise as functionals of recursive structures, of random trees or in recursive algorithms. In particular they arise in the worst case analysis of divide and conquer algorithms, in parallel search algorithms or in the height of random tree models. For the proof we determine asymptotic bounds for the moments or for the Laplace transforms and apply a characterization of exponential tail bounds due to Kasahara (1978).

关键词： recursive algorithm exponential bounds divide and conquer algorithm probabilistic analysis of algorithms

来源：评论

学校读者我要写书评

暂无评论

Profiles of random trees: Limit theorems for random recursive trees and binary search trees

引用

ALGORITHMICA 2006年第3-4期46卷 367-407页

作者： Fuchs, Michael Hwang, Hsien-Kuei Neininger, Ralph Natl Chiao Tung Univ Dept Appl Math Hsinchu 300 Taiwan Acad Sinica Inst Stat Sci Taipei 115 Taiwan Goethe Univ Frankfurt Dept Math D-60325 Frankfurt AM Germany

We prove convergence in distribution for the profile (the number of nodes at each level), normalized by its mean, of random recursive trees when the limit ratio alpha of the level and the logarithm of tree size lies in [0, e). Convergence of all moments is shown to hold only for a E [0, 1] (with only convergence of finite moments when alpha is an element of (1, e)). When the limit ratio is 0 or 1 for which the limit laws are both constant, we prove asymptotic normality for alpha = 0 and a "quicksort type" limit law for alpha = 1, the latter case having additionally a small range where there is no fixed limit law. Our tools are based on the contraction method and method of moments. Similar phenomena also hold for other classes of trees;we apply our tools to binary search trees and give a complete characterization of the profile. The profiles of these random trees represent concrete examples for which the range of convergence in distribution differs from that of convergence of all moments.

关键词： random recursive tree random binary search tree profile of trees probabilistic analysis of algorithms weak convergence

来源：评论

学校读者我要写书评

暂无评论

Profiles of random trees: Limit theorems for random recursive trees and binary search trees

Profiles of random trees: Limit theorems for random recursiv...

引用

10th Workshop on the analysis of algorithms

关键词： random recursive tree random binary search tree profile of trees probabilistic analysis of algorithms weak convergence

来源：评论

学校读者我要写书评

暂无评论

Euclidean algorithms are Gaussian

引用

JOURNAL OF NUMBER THEORY 2005年第2期110卷 331-386页

作者： Baladi, V Vallée, B Univ Paris 07 CNRS Inst Math Jussieu UMR 7586 F-75251 Paris 05 France Univ Caen CNRS UMR 6072 F-14032 Caen France

We obtain a central limit theorem for a general class of additive parameters (costs, observables) associated to three standard Euclidean algorithms, with optimal speed of convergence. We also provide very precise asymptotic estimates and error terms for the mean and variance of such parameters. For costs that are lattice (including the number of steps), we go further and establish a local limit theorem, with optimal speed of convergence. We view an algorithm as a dynamical system restricted to rational inputs, and combine tools imported from dynamics, such as transfer operators, with various other techniques: Dirichlet series, Perron's formula, quasi-powers theorems, and the saddle-point method. Such dynamical analyses had previously been used to perform the average-case analysis of algorithms. For the present (dynamical) analysis in distribution, we require estimates on transfer operators when a parameter varies along vertical lines in the complex plane. To prove them, we adapt techniques introduced recently by Dolgopyat in the context of continuous-time dynamics (Ann. Math. 147 (1998) 357). (C) 2004 Elsevier Inc. All rights reserved.

关键词： probabilistic analysis of algorithms dynamical systems transfer operator Dirichlet series Perron's formula central limit theorem local limit theorem

来源：评论

学校读者我要写书评

暂无评论

A survey of Max-type recursive distributional equations

引用

ANNALS OF APPLIED PROBABILITY 2005年第2期15卷 1047-1110页

作者： Aldous, DJ Bandyopadhyay, A Univ Calif Berkeley Dept Stat Berkeley CA 94720 USA Univ Minnesota Inst Math & Applicat Minneapolis MN 55414 USA

In certain problems in a variety of applied probability settings (from probabilistic analysis of algorithms to statistical physics), the central requirement is to solve a recursive distributional equation of the form X-d = g((xi(i), X-i), i >= 1). Here (xi(i)) and g((.)) are given and the X-i are independent copies of the unknown distribution X. We survey this area, emphasizing examples where the function g((.)) is essentially a "maximum" or "minimum" function. We draw attention to the theoretical question of endogeny: in the associated recursive tree process X-i, are the X-i measurable functions of the innovations process (xi(i))?

关键词： branching process branching random walk cavity method coupling from the past fixed point equation frozen percolation mean-field model of distance metric contraction probabilistic analysis of algorithms probability distribution probability on trees random matching

来源：评论

学校读者我要写书评

暂无评论

On worst-case Robin Hood hashing

引用

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

来源：评论

学校读者我要写书评

暂无评论

Cuckoo hashing: Further analysis

引用

INFORMATION PROCESSING LETTERS 2003年第4期86卷 215-219页

作者： Devroye, L Morin, P McGill Univ Sch Comp Sci Montreal PQ H3A 2K6 Canada

We consider cuckoo hashing as proposed by Pagh and Rodler in 2001. We show that the expected construction time of the hash table is O(n) as long as the two open addressing tables are each of size at least (1 + epsilon)n, where epsilon > 0 and n is the number of data points. Slightly improved bounds are obtained for various probabilities and constraints. The analysis rests on simple properties of branching processes. (C) 2003 Elsevier Science B.V. All rights reserved.

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

来源：评论

学校读者我要写书评

暂无评论

Random suffix search trees

引用

RANDOM STRUCTURES & algorithms 2003年第4期23卷 357-396页

作者： Devroye, L Neininger, R McGill Univ Sch Comp Sci Montreal PQ H3A 2K6 Canada

A random suffix search tree is a binary search tree constructed for the suffixes X(i) = 0 (.) B(i)B(i+1)B(i+2)... of a sequence B(1), B(2), B(3),... of independent identically distributed random b-ary digits B(j). Let D(n) denote the depth of the node for X(n) in this tree when B(1) is uniform on Z(b). We show that for any value of b > 1, ED(n) = 2 log n + O(log(2)log n), just as for the random binary search tree. We also show that D(n)/ED(n) --> 1 in probability. (C) 2003 Wiley Periodicals, Inc.

关键词： random binary search tree suffix tree Lacunary sequences random spacings probabilistic analysis of algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：