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     

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.     

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     

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     

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.     

Oscillations in the height of the Yule tree and application to the binary search tree

For a particular case of a branching random walk with lattice support, namely the Yule branching random walk, we prove that the distribution of the centred maximum oscillates around a distribution corresponding to a critical travelling wave in the following sense: there exist continuous functions and such that: where and is the height of the Yule tree. We also shows that similar oscillations occur for , when f is in a large class of functions. This process is classically related to the binary search tree, thus yielding analogous results for the height and for the saturation level of the binary search tree. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 51, 90–120, 2017     

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.     

Optimal binary search methods

The ordinary binary search method is shown to be one of a class of optimal binary search methods, supposing equiprobable search keys. For certain values of the numbern of records this class may be rather large. Thus forn=2 ^K +2 ^K–1–1 the number of optimal methods is of order 2^2n/3.     

One-sided variations on binary search trees

We investigate incomplete one-sided variants of binary search trees. The (normed) size of each variant is studied, and convergence to a Gaussian law is proved in each case by asymptotically solving recurrences. These variations are also discussed within the scope of the contraction method with degenerate limit equations. In an incomplete tree the size determines most other parameters of interest, such as the height and the internal path length.     

A parameter-free self-adapting boundary genetic search for pipe network optimization

Commercial application of genetic algorithms (GAs) to engineering design problems, including optimal design of pipe networks, could be facilitated by the development of algorithms that require the least number of parameter tuning. This paper presents an attempt to eliminate the need for defining a priori the proper penalty parameter in GA search for pipe networks optimal designs. The method is based on the assumption that the optimal solution of a pipe network design problem lies somewhere on, or near, the boundary of the feasible region. The proposed method uses the ratio of the best feasible and infeasible designs at each generation to guide the direction of the search towards the boundary of the feasible domain by automatically adjusting the value of the penalty parameter. The value of the ratio greater than unity is interpreted as the search being performed in the feasible region and vice versa. The new adapted value of the penalty parameter at each generation is therefore calculated as the product of its current value and the aforementioned ratio. The genetic search so constructed is shown to converge to the boundary of the feasible region irrespective of the starting value of the constraint violation penalty parameter. The proposed method is described here in the context of pipe network optimisation problems but is equally applicable to any other constrained optimisation problem. The effectiveness of the method is illustrated with a benchmark pipe network optimization example from the literature.     

A hybrid genetic local search algorithm for the permutation flowshop scheduling problem

Traditionally, the permutation flowshop scheduling problem (PFSP) was with the criterion of minimizing makespan. The permutation flowshop scheduling problem to minimize the total flowtime has attracted more attention from researchers in recent years. In this paper, a hybrid genetic local search algorithm is proposed to solve this problem with each of both criteria. The proposed algorithm hybridizes the genetic algorithm and a novel local search scheme that combines two local search methods: the Insertion Search (IS) and the Insertion Search with Cut-and-Repair (ISCR). It employs the genetic algorithm to do the global search and two local search methods to do the local search. Two local search methods play different roles in the search process. The Insertion Search is responsible for searching a small neighborhood while the Insertion Search with Cut-and-Repair is responsible for searching a large neighborhood. Furthermore, the orthogonal-array-based crossover operator is designed to enhance the GA’s capability of intensification. The experimental results show the advantage of combining the two local search methods. The performance of the proposed hybrid genetic algorithm is very competitive. For the PFSP with the total flowtime criterion, it improved 66 out of the 90 current best solutions reported in the literature in short-term search and it also improved all the 20 current best solutions reported in the literature in long-term search. For the PFSP with the makespan criterion, the proposed algorithm also outperforms the other three methods recently reported in the literature.     

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 approach for solving linear bilevel problems using genetic algorithms

Bilevel programming involves two optimization problems where the constraint region of the first level problem is implicitly determined by another optimization problem. This paper develops a genetic algorithm for the linear bilevel problem in which both objective functions are linear and the common constraint region is a polyhedron. Taking into account the existence of an extreme point of the polyhedron which solves the problem, the algorithm aims to combine classical extreme point enumeration techniques with genetic search methods by associating chromosomes with extreme points of the polyhedron. The numerical results show the efficiency of the proposed algorithm. In addition, this genetic algorithm can also be used for solving quasiconcave bilevel problems provided that the second level objective function is linear.     

A tabu search and a genetic algorithm for solving a bicriteria general job shop scheduling problem

This paper deals with a general job shop scheduling problem with multiple constraints, coming from printing and boarding industry. The objective is the minimization of two criteria, the makespan and the maximum lateness, and we are interested in finding an approximation of the Pareto frontier. We propose a fast and elitist genetic algorithm based on NSGA-II for solving the problem. The initial population of this algorithm is either randomly generated or partially generated by using a tabu search algorithm, that minimizes a linear combination of the two criteria. Both the genetic and the tabu search algorithms are tested on benchmark instances from flexible job shop literature and computational results show the interest of both methods to obtain an efficient and effective resolution method.     

A study of random Weyl trees

We study binary search trees constructed from Weyl sequences {nθ}, n≥1, where θ is an irrational and {·} denotes “mod 1.” We explore various properties of the structure of these trees, and relate them to the continued fraction expansion of θ. If H_n is the height of the tree with n nodes when θ is chosen at random and uniformly on [0, 1], then we show that in probability, H_n∼(12/π²)log n log log n. © 1998 John Wiley & Sons, Inc. Random Struct. Alg., 12, 271–295, 1998     

Selection by rank in K‐dimensional binary search trees

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 for or , and for (with ), where depends on the dimension K and the variant of K‐d tree under consideration. We also show that Select‐by‐Rank visits nodes on average, where is the given rank and the exponent α is as above. We give the explicit form of the functions and , both are bounded in [0, 1] and they depend on K, on the variant of K‐d tree under consideration, and, eventually, on the specific coordinate j for which we execute our algorithms. 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. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 45, 14–37, 2014     

A sufficient condition for near-optimal stochastic controls and its application to manufacturing systems

This paper presents an asymptotic analysis of control models governed by stochastic ordinary differential equations. A sufficient condition of near-optimal controls is given based on Ekeland's principle. It is shown that, under some concavity assumptions, the-maximum condition in terms of the Hamiltonian implies the -optimality. By applying this result to a general manufacturing system, the common practice of hierarchical controls employed in order to reduce the overall complexity of the system is justified on a rigorous basis. A near-optimal control for the operational level is constructed from a near-optimal control at the corporate level, and an asymptotic error bound is obtained. A stochastic extension of the classical HMMS model is treated as a specific example. The approach of this paper is different from those in the literature, and it allows us to handle some previously unsolved problems with nonlinear state equations as well as nonseparable cost functions.This work was partly supported by NSERC Grant A4619, URIF, and the Manufacturing Research Corporation of Ontario.     

A new linear programming approach and genetic algorithm for solving airline boarding problem

The airline industry is under intense competition to simultaneously increase efficiency and satisfaction for passengers and profitability and internal system benefit for itself. The boarding process is one way to achieve these objectives as it tends itself to adaptive changes. In order to increase the flying time of a plane, commercial airlines try to minimize the boarding time, which is one of the most lengthy parts of a plane’s turn time. To reduce boarding time, it is thus necessary to minimize the number of interferences between passengers by controlling the order in which they get onto the plane through a boarding policy. Here, we determine the passenger boarding problem and examine the different kinds of passenger boarding strategies and boarding interferences in a single aisle aircraft. We offer a new integer linear programming approach to reduce the passenger boarding time. A genetic algorithm is used to solve this problem. Numerical results show effectiveness of the proposed algorithm.     

A composite-neighborhood tabu search approach to the traveling tournament problem

The Traveling Tournament Problem (TTP) is a combinatorial problem that combines features from the traveling salesman problem and the tournament scheduling problem. We propose a family of tabu search solvers for the solution of TTP that make use of complex combination of many neighborhood structures. The different neighborhoods have been thoroughly analyzed and experimentally compared. We evaluate the solvers on three sets of publicly available benchmarks and we show a comparison of their outcomes with previous results presented in the literature. The results show that our algorithm is competitive with those in the literature.