AbstractLet us consider an ordered set of keys A={a1<⋯<an}, where the probability of searching ai is 1/n, for i=1,…,n. If the cost of testing each key is similar, then the standard binary search is the strategy with minimum expected access cost. However, if the cost of testing ai is ci, for i=1,…,n, then the standard binary search is not necessarily the best strategy.In this paper, we prove that the expected access cost of an optimal search strategy is bounded above by 4Cln(n+1)/n, where C=∑i=1nci. Furthermore, we show that this upper bound is asymptotically tight up to constant factors. The proof of this upper bound is constructive and generates a 4ln(n+1)-approximated algorithm for constructing near-optimal search strategies. This algorit...
In this paper we provide new lower bounds on the cost C of binary search trees. The bounds are expre...
We consider the problem of finding edge search strategies of minimum cost. The cost of a search stra...
Many important problems in operations research, artificial intelligence, combinatorial algorithms, a...
AbstractLet us consider an ordered set of keys A={a1<⋯<an}, where the probability of searching ai is...
Submitted by Elaine Almeida (elaine.almeida@nce.ufrj.br) on 2017-08-04T13:14:30Z No. of bitstreams:...
AbstractA satisficing search problem consists of a set of probabilistic experiments to be performed ...
AbstractWe describe algorithms for constructing optimal binary search trees, in which the access cos...
AbstractWe consider the problem of building optimal binary search trees. The binary search tree is a...
This paper considers the problem of bounding below the cost of accessing a sequence of keys in a bin...
The dynamic optimality conjecture is perhaps the most fundamental open question about binary search ...
Many important problems are too difficult to solve optimally. A traditional approach to such problem...
We present lower and upper bounds on adaptive heuristics for main-taining binary search trees using ...
This paper focuses on competitive function evaluation in the context of computing with priced inform...
Binary search trees (BSTs) with rotations can adapt to various kinds of structure in search sequence...
Abstract. In 1971, Knuth gave an O(n2)-time algorithm for the clas-sic problem of finding an optimal...
In this paper we provide new lower bounds on the cost C of binary search trees. The bounds are expre...
We consider the problem of finding edge search strategies of minimum cost. The cost of a search stra...
Many important problems in operations research, artificial intelligence, combinatorial algorithms, a...
AbstractLet us consider an ordered set of keys A={a1<⋯<an}, where the probability of searching ai is...
Submitted by Elaine Almeida (elaine.almeida@nce.ufrj.br) on 2017-08-04T13:14:30Z No. of bitstreams:...
AbstractA satisficing search problem consists of a set of probabilistic experiments to be performed ...
AbstractWe describe algorithms for constructing optimal binary search trees, in which the access cos...
AbstractWe consider the problem of building optimal binary search trees. The binary search tree is a...
This paper considers the problem of bounding below the cost of accessing a sequence of keys in a bin...
The dynamic optimality conjecture is perhaps the most fundamental open question about binary search ...
Many important problems are too difficult to solve optimally. A traditional approach to such problem...
We present lower and upper bounds on adaptive heuristics for main-taining binary search trees using ...
This paper focuses on competitive function evaluation in the context of computing with priced inform...
Binary search trees (BSTs) with rotations can adapt to various kinds of structure in search sequence...
Abstract. In 1971, Knuth gave an O(n2)-time algorithm for the clas-sic problem of finding an optimal...
In this paper we provide new lower bounds on the cost C of binary search trees. The bounds are expre...
We consider the problem of finding edge search strategies of minimum cost. The cost of a search stra...
Many important problems in operations research, artificial intelligence, combinatorial algorithms, a...