An almost optimal algorithm for unbounded searching
From MaRDI portal
Publication:1229581
DOI10.1016/0020-0190(76)90071-5zbMath0335.68030OpenAlexW1975489634WikidataQ57254330 ScholiaQ57254330MaRDI QIDQ1229581
Andrew Chi-Chih Yao, Jon Louis Bentley
Publication date: 1976
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(76)90071-5
Related Items (42)
Online scheduling with partial job values: does timesharing or randomization help? ⋮ Improved algorithms for group testing with inhibitors ⋮ The complexity of finding SUBSEQ\((A)\) ⋮ The longest common subsequence problem revisited ⋮ How to Share a Secret, Infinitely ⋮ Refined algorithms for hitting many intervals ⋮ Searching with known error probability ⋮ Techniques for parallel manipulation of sparse matrices ⋮ Minimal sets on propositional formulae. Problems and reductions ⋮ Unbounded search and recursive graph problems ⋮ On compressing permutations and adaptive sorting ⋮ Binary search and recursive graph problems ⋮ An instance-based algorithm for deciding the bias of a coin ⋮ Fast calculation of p-values for one-sided Kolmogorov-Smirnov type statistics ⋮ Data Structures for Data-Intensive Applications: Tradeoffs and Design Guidelines ⋮ A Wait-free Queue with Polylogarithmic Step Complexity ⋮ The complexity of selection and ranking in X+Y and matrices with sorted columns ⋮ Toward more localized local algorithms: removing assumptions concerning global knowledge ⋮ On the complexity of finding the chromatic number of a recursive graph. II: The unbounded case ⋮ Fast sequential and parallel algorithms for finding extremal sets ⋮ On short fastest paths in temporal graphs ⋮ Quantum key search with side channel advice ⋮ A Faster Subquadratic Algorithm for the Longest Common Increasing Subsequence Problem ⋮ Randomized mutual exclusion on a multiple access channel ⋮ Adaptive sorting: an information theoretic perspective ⋮ Efficient algorithms for chemical threshold testing problems ⋮ Optimal encoding of non-stationary sources ⋮ Estimation of distributions involving unobservable events: the case of optimal search with unknown target distributions ⋮ Optimal prefix codes with fewer distinct codeword lengths are faster to construct ⋮ A satisfiability and workload-based exact method for the resource constrained project scheduling problem with generalized precedence constraints ⋮ Searching games with errors -- fifty years of coping with liars ⋮ On computing distances between leaves in a complete tree ⋮ Tracing compressed curves in triangulated surfaces ⋮ Finger search in grammar-compressed strings ⋮ Fast scalable construction of ([compressed static | minimal perfect hash) functions] ⋮ Integer representation in the mixed base \((2,3)\) ⋮ Range minimum queries in minimal space ⋮ A general class of resource tradeoffs ⋮ From Time to Space: Fast Algorithms That Yield Small and Fast Data Structures ⋮ Searching and encoding for infinite ordered sets ⋮ Space-efficient Huffman codes revisited ⋮ How many probes are needed to compute the maximum of a random walk?
Cites Work
This page was built for publication: An almost optimal algorithm for unbounded searching
