On the height of random m-ary search trees

A random m-ary seach tree is constructed from a random permutation of 1,…, n. A law of large numbers is obtained for the height H_n of these trees by applying the theory of branching random walks. in particular, it is shown that H_n/log n→γ in probability as n→∞ where γ = γ(m) is a constant depending upon m only. Interestingly, as m→∞, γ(m) is asymptotic to 1/log m, the coefficient of log n in the asymptotic expression for the height of the complete m-ary search tree. This proves that for large m, random m-ary search trees behave virtually like complete m-ary trees.     

Patterns in random binary search trees

In a randomly grown binary search tree (BST) of size n, any fixed pattern occurs with a frequency that is on average proportional to n. Deviations from the average case are highly unlikely and well quantified by a Gaussian law. Trees with forbidden patterns occur with an exponentially small probability that is characterized in terms of Bessel functions. The results obtained extend to BSTs a type of property otherwise known for strings and combinatorial tree models. They apply to paged trees or to quicksort with halting on short subfiles. As a consequence, various pointer saving strategies for maintaining trees obeying the random BST model can be precisely quantified. The methods used are based on analytic models, especially bivariate generating function subjected to singularity perturbation asymptotics. © 1997 John Wiley & Sons, Inc. Random Struct. Alg., 11 : 223–244, 1997     

The suffix binary search tree and suffix AVL tree

Suffix trees and suffix arrays are classical data structures that are used to represent the set of suffixes of a given string, and thereby facilitate the efficient solution of various string processing problems—in particular on-line string searching. Here we investigate the potential of suitably adapted binary search trees as competitors in this context. The suffix binary search tree (SBST) and its balanced counterpart, the suffix AVL-tree, are conceptually simple, relatively easy to implement, and offer time and space efficiency to rival suffix trees and suffix arrays, with distinct advantages in some circumstances—for instance in cases where only a subset of the suffixes need be represented.

Construction of a suffix BST for an n-long string can be achieved in O(nh) time, where h is the height of the tree. In the case of a suffix AVL-tree this will be O(nlogn) in the worst case. Searching for an m-long substring requires O(m+l) time, where l is the length of the search path. In the suffix AVL-tree this is O(m+logn) in the worst case. The space requirements are linear in n, generally intermediate between those for a suffix tree and a suffix array.

Empirical evidence, illustrating the competitiveness of suffix BSTs, is presented.     

A new genetic approach to construct near-optimal binary search trees

Many definitive and approximate methods have been so far proposed for the construction of an optimal binary search tree. One such method is the use of evolutionary algorithms with satisfactorily improved cost efficiencies. This paper will propose a new genetic algorithm for making a near-optimal binary search tree. In this algorithm, a new greedy method is used for the crossover of chromosomes while a new way is also developed for inducing mutation in them. Practical results show a rapid and desirable convergence towards the near-optimal solution. The use of a heuristic to create not so costly chromosomes as the first offspring, the greediness of the crossover, and the application of elitism in the selection of future generation chromosomes are the most important factors leading to near-optimal solutions by the algorithm at desirably high speeds. Due to the practical results, increasing problem size does not cause any considerable difference between the solution obtained from the algorithm and exact solution.     

Random sequential bisection and its associated binary tree

Summary Random sequential bisection is a process to divide a given interval into two, four, eight, ... parts at random. Each division point is uniformly distributed on the interval and conditionally independent of the others. To study the asymptotic behavior of the lengths of subintervals in random seqential bisection, the associated binary tree is introduced. The number of internal or external nodes of the tree is asymptotically normal. The levels of the lowest and the highest external nodes are bounded with probability one or with probability increasing to one as the number of nodes increases to infinity. The associated binary tree is closely related to random binary tree which arises in computer algorithms, such as binary search tree and quicksort, and one-dimensional packing or the parking problem.     

Limit laws for local counters in random binary search trees

Limit laws for several quantities in random binary search trees that are related to the local shape of a tree around each node can be obtained very simply by applying central limit theorems for w-dependent random variables. Examples include: the number of leaves (L_n), the number of nodes with k descendants (k fixed), the number of nodes with no left child, the number of nodes with k left descendants. Some of these results can also be obtained via the theory of urn models, but the present method seems easier to apply.     

Martingales and large deviations for binary search trees

We establish an almost sure large deviations theorem for the depth of the external nodes of binary search trees (BSTs). To achieve this, a parametric family of martingales is introduced. This family also allows us to get asymptotic results on the number of external nodes at deepest level. © 2001 John Wiley & Sons, Inc. Random Struct. Alg., 19: 112–127, 2001     

A phase transition for the heights of a fragmentation tree

We provide information about the asymptotic regimes for a homogeneous fragmentation of a finite set. We establish a phase transition for the asymptotic behavior of the shattering times, defined as the first instants when all the blocks of the partition process have cardinality less than a fixed integer. Our results may be applied to the study of certain random split trees. © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 39, 247‐274, 2011     

On optimal search plans to detect a target moving randomly on the real line

A target, whose initial position is unknown, is performing a random walk on the integers. A searcher, starting at the origin, wants to follow a search plan for which E[τ^k] is finite, where k ≥ 1 and τ is the time to capture. The searcher, who has a prior distribution over the target's initial position, can move only to adjacent positions, and cannot travel faster than the target. Necessary and sufficient conditions are given for the existence of search plans for which E[τ^k] is finite and a minimum.     

Limiting theorems for the nodes in binary search trees

We consider three random variables X_n, Y_n and Z_n, which represent the numbers of the nodes with 0, 1, and 2 children, in the binary search trees of size n. The expectation and variance of the three above random variables are got, and it is also shown that X_n, Y_n and Z_n are all asymptotically normal as n→∞by applying the contraction method.     

Random suffix search trees

A random suffix search tree is a binary search tree constructed for the suffixes X_i = 0 · B_iB_i+1B_i+2… of a sequence B₁, B₂, B₃, … 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₁ is uniform on ?_b. We show that for any value of b > 1, ??D_n = 2 log n + O(log²log n), just as for the random binary search tree. We also show that D_n/??D_n → 1 in probability. © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 2003     

A tabu search heuristic for the generalized minimum spanning tree problem

This paper describes an attribute based tabu search heuristic for the generalized minimum spanning tree problem (GMSTP) known to be NP-hard. Given a graph whose vertex set is partitioned into clusters, the GMSTP consists of designing a minimum cost tree spanning all clusters. An attribute based tabu search heuristic employing new neighborhoods is proposed. An extended set of TSPLIB test instances for the GMSTP is generated and the heuristic is compared with recently proposed genetic algorithms. The proposed heuristic yields the best results for all instances. Moreover, an adaptation of the tabu search algorithm is proposed for a variation of the GMSTP in which each cluster must be spanned at least once.     

On total progeny of multitype Galton-Watson process and the first passage time of random walk on lattice

In this paper,we form a method to calculate the probability generating function of the total progeny of multitype branching process.As examples,we calculate probability generating function of the total progeny of the multitype branching processes within random walk which could stay at its position and(2-1) random walk.Consequently,we could give the probability generating functions and the distributions of the first passage time of corresponding random walks.Especially,for recurrent random walk which could stay at its position with probability 0 r 1,we show that the tail probability of the first passage time decays as 2/(π(1-r)~(1/2)) n~(1/1)= when n →∞.     

The distribution of height and diameter in random non‐plane binary trees

This study is dedicated to precise distributional analyses of the height of non‐plane unlabelled binary trees (“Otter trees”), when trees of a given size are taken with equal likelihood. The height of a rooted tree of size n is proved to admit a limiting theta distribution, both in a central and local sense, and obey moderate as well as large deviations estimates. The approximations obtained for height also yield the limiting distribution of the diameter of unrooted trees. The proofs rely on a precise analysis, in the complex plane and near singularities, of generating functions associated with trees of bounded height. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2012     

Local search and suffix tree for car-sequencing problem with colors

This paper describes an approximation solution method for the car sequencing problem with colors. Firstly, we study the optimality of problems with a single ratio constraint. This study also introduces a data structure for efficient calculation of the penalties related to ratio constraints. We describe the constructive greedy algorithm and variable neighborhood search adjusted for the problem with colors. Tabu metaheuristic is used to improve the results obtained by VNS. We then represent the cars with their constraints as letters over an alphabet and apply the algorithm to spell the motifs in order to improve the number of batch colors without decreasing the costs associated to the set of ratio constraints. The algorithm achieves 19 out of the 64 best results for instance sets A and B. These instances are the reference instances for Challenge ROADEF.     

Properties of the random search in global optimization

From theorems which we prove about the behavior of gaps in a set ofN uniformly random points on the interval [0, 1], we determine properties of the random search procedure in one-dimensional global optimization. In particular, we show that the uniform grid search is better than the random search when the optimum is chosen using the deterministic strategy, that a significant proportion of large gaps are contained in the uniformly random search, and that the error in the determination of the point at which the optimum occurs, assuming that it is unique, will on the average be twice as large using the uniformly random search compared with the uniform grid. In addition, some of the properties of the largest gap are verified numerically, and some extensions to higher dimensions are discussed. The latter show that not all of the conclusions derived concerning the inadequacies of the one-dimensional random search extend to higher dimensions, and thaton average the random search is better than the uniform grid for dimensions greater than 6.This paper is based on work started in the Statistics Department of Princeton University when the first author was visiting as a Research Associate. Part of this research was supported by the Office of Naval Research, Contract No. 0014-67-A-0151-0017, and by the US Army Research Office—Durham, Contract No. DA-31-124-ARO-D-215.2 The authors wish to thank B. Omodei for his careful work in preparing the programs for the results of Figs. 1–2 and Table 1. The computations were performed on the IBM 360/50 of the Australian National University's Computer Centre. Thanks are also due to R. Miles for suggestions regarding the extension of the results to multidimensional regions, and to P. A. P. Moran and R. Brent for suggestions regarding the evaluation of the integral ₀ ¹ ... ^0/1 (x ₁ ² + ... +x _n ^/2 )^1/2 dx ₁ ...dx _n.     

Majorizing kernels and stochastic cascades with applications to incompressible Navier-Stokes equations

A general method is developed to obtain conditions on initial data and forcing terms for the global existence of unique regular solutions to incompressible 3d Navier-Stokes equations. The basic idea generalizes a probabilistic approach introduced by LeJan and Sznitman (1997) to obtain weak solutions whose Fourier transform may be represented by an expected value of a stochastic cascade. A functional analytic framework is also developed which partially connects stochastic iterations and certain Picard iterates. Some local existence and uniqueness results are also obtained by contractive mapping conditions on the Picard iteration.

     

Breakout local search for the Steiner tree problem with revenue,budget and hop constraints

The Steiner tree problem (STP) is one of the most popular combinatorial optimization problems with various practical applications. In this paper, we propose a Breakout Local Search (BLS) algorithm for an important generalization of the STP: the Steiner tree problem with revenue, budget and hop constraints (STPRBH), which consists of determining a subtree of a given undirected graph which maximizes the collected revenues, subject to both budget and hop constraints. Starting from a probabilistically constructed initial solution, BLS uses a Neighborhood Search (NS) procedure based on several specifically designed move operators for local optimization, and employs an adaptive diversification strategy to escape from local optima. The diversification mechanism is implemented by adaptive perturbations, guided by dedicated information of discovered high-quality solutions. Computational results based on 240 benchmarks show that BLS produces competitive results with respect to several previous approaches. For the 56 most challenging instances with unknown optimal results, BLS succeeds in improving 49 and matching one best known results within reasonable time. For the 184 instances which have been solved to optimality, BLS can also match 167 optimal results.     

二叉树上分枝马氏链的强大数定理

首先给出了在可列状态空间取值的二叉树上分枝马氏链定义的离散形式,然后建立了二叉树上分枝马氏链的若干强极限定理,最后研究了二叉树上有限状态分枝马氏链的强大数定理．