In this paper we investigate the average Horton-Strahler number of all possible tree-structures of binary tries. For that purpose we consider a generalization of extended binary trees where leaves are distinguished in order to represent the location of keys within a corresponding trie. Assuming a uniform distribution for those trees we prove that the expected Horton-Strahler number of a tree with α internal nodes and β leaves that correspond to a key is asymptotically given by $$\frac{4^{2\beta -\alpha }log\left(\alpha \right)(2\beta -1)(\alpha +1)(\alpha +2)\left(\genfrac{}{}{0pt}{}{2\alpha +1}{\alpha -1}\right)}{8\sqrt{\pi }{\alpha }^{3/2}log\left(2\right)(\beta -1)\beta {\left(\genfrac{}{}{0pt}{}{2\beta }{\beta }\right)}^2}$$ provided that α...

In the job shop scheduling problem $k$-units-$J_m$, there are $m$ machines and each machine has an integer processing time of at most $k$ time units. Each job consists of a permutation of $m$ tasks corresponding to all machines and thus all jobs have an identical dilation $D$. The contribution of this paper are the following results; (i) for $d=o\left(\sqrt{D}\right)$ jobs and every fixed $k$, the makespan of an optimal schedule is at most $D+o\left(D\right)$, which extends the result of [3] for $k=1$; (ii) a randomized on-line approximation algorithm for $k$-units-...

In the job shop scheduling problem k-units-Jm, there are m machines and each machine has an integer processing time of at most k time units. Each job consists of a permutation of m tasks corresponding to all machines and thus all jobs have an identical dilation D. The contribution of this paper are the following results; (i) for $d=o\left(\sqrt{D}\right)$ jobs and every fixed k, the makespan of an optimal schedule is at most D+ o(D), which extends the result of [3] for k=1; (ii) a randomized on-line approximation...

For p ≤ n, let b1(n),...,bp(n) be independent random vectors in ${ℝ}^n$ with the same distribution invariant by rotation and without mass at the origin. Almost surely these vectors form a basis for the Euclidean lattice they generate. The topic of this paper is the property of reduction of this random basis in the sense of Lenstra-Lenstra-Lovász (LLL). If ${\widehat{b}}_1^{\left(n\right)},...,{\widehat{b}}_p^{\left(n\right)}$ is the basis obtained from b1(n),...,bp(n) by Gram-Schmidt orthogonalization, the quality of the reduction depends upon the sequence of ratios...

Digital trees or tries are a general purpose flexible data structure that implements dictionaries built on words. The present paper is focussed on the average-case analysis of an important parameter of this tree-structure, i.e., the stack-size. The stack-size of a tree is the memory needed by a storage-optimal preorder traversal. The analysis is carried out under a general model in which words are produced by a source (in the information-theoretic sense) that emits symbols. Under some natural assumptions...

Digital trees or tries are a general purpose flexible data structure that implements dictionaries built on words. The present paper is focussed on the average-case analysis of an important parameter of this tree-structure, i.e., the stack-size. The stack-size of a tree is the memory needed by a storage-optimal preorder traversal. The analysis is carried out under a general model in which words are produced by a source (in the information-theoretic sense) that emits symbols. Under some natural...