An optimal algorithm for finding all the jumps of a monotone step-function

DOI10.1016/0196-6774(85)90043-4MaRDI QIDQ3723701zbMATH OpenOpenAlexFDO

Authors Refael Hassin, Nimrod Megiddo

Publication date 1985

Published in Journal of Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0196-6774(85)90043-4

zbMATH Keywords

binary search

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) 2-person games (91A05)

Recommendations

• scientific article; zbMATH DE number 3974158
• On an approximation algorithm using step functions
• An optimal algorithm to find the jump number of partially ordered sets
• An optimal deciphering algorithm for some classes of monotonic functions
• An algorithm for computing estimators that optimize step functions
• An optimal single-step algorithm for maximizing doubly differentiable functions
• An approximate dynamic programming algorithm for monotone value functions
• An alogrithm for monotonic global optimization problems^∗
• scientific article; zbMATH DE number 4204285
• scientific article; zbMATH DE number 7079312

Cited in

(8)

• Searching for a monotone function by independent threshold queries
• Jumping Doesn’t Help in Abstract Cubes
• Optimal jumping patterns
• Operations research applications of dichotomous search
• A generalization of binary search
• Optimal search for rationals
• An optimal parallel algorithm for digital curve segmentation using hough polygons and monotone function search
• An optimal parallel algorithm for digital curve segmentation

This page was built for publication: An optimal algorithm for finding all the jumps of a monotone step-function

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