Generalized Kraft’s Inequality and Discrete k-Modal Search

DOI10.1137/S0097539793246367MaRDI QIDQ4877528zbMATH OpenOpenAlexFDO

Authors Anmol Mathur, Edward M. Reingold

Publication date 18 August 1996

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s0097539793246367

zbMATH Keywords

\(k\)-modal functionKraft's inequality

Mathematics Subject Classification ID

Fibonacci and Lucas numbers and polynomials and generalizations (11B39) Analysis of algorithms and problem complexity (68Q25) Parallel algorithms in computer science (68W10)

Recommendations

• A Fibonacci Version of Kraft’s Inequality Applied to Discrete Unimodal Search
• More Nearly Optimal Algorithms for Unbounded Searching, Part I: The Finite Case
• A generalization of binary search
• scientific article; zbMATH DE number 3958602
• An optimal algorithm for finding all the jumps of a monotone step-function

Cited in

(6)

• Approximate location of relevant variables under the crossover distribution.
• How many probes are needed to compute the maximum of a random walk?
• An upper bound on the k-modem illumination problem
• A Fibonacci Version of Kraft’s Inequality Applied to Discrete Unimodal Search
• Searching games with errors -- fifty years of coping with liars
• Precision, local search and unimodal functions

This page was built for publication: Generalized Kraft’s Inequality and Discrete k-Modal Search

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4877528)