𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the query complexity of finding a local maximum point

✍ Scribed by A.L. Rastsvetaev; L.D. Beklemishev

Publisher
Elsevier Science
Year
2002
Tongue
English
Weight
94 KB
Volume
84
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

✦ Synopsis

We calculate the minimal number of queries sufficient to find a local maximum point of a function on a discrete interval, for a model with M parallel queries, M 1. Matching upper and lower bounds are obtained. The bounds are formulated in terms of certain Fibonacci type sequences of numbers.

πŸ“œ SIMILAR VOLUMES

On the complexity of finding a local max
On the complexity of finding a local maximum of functions on discrete planar subsets
✍ Anton Mityagin πŸ“‚ Article πŸ“… 2004 πŸ› Elsevier Science 🌐 English βš– 237 KB

We study how many values of an unknown integer-valued function f one needs to know in order to ΓΏnd a local maximum of f. We consider functions deΓΏned on ΓΏnite subsets of discrete plane. We prove upper bounds for functions deΓΏned on rectangles and present lower bounds for functions deΓΏned on arbitrar

On the Query Complexity of Clique Size a
On the Query Complexity of Clique Size and Maximum Satisfiability
✍ Richard Chang πŸ“‚ Article πŸ“… 1996 πŸ› Elsevier Science 🌐 English βš– 682 KB

This paper explores the bounded query complexity of approximating the size of the maximum clique in a graph (Clique Size) and the number of simultaneously satisfiable clauses in a 3CNF formula (MaxSat). The results in the paper show that for certain approximation factors, approximating Clique Size a

On the Exact Worst Case Query Complexity
On the Exact Worst Case Query Complexity of Planar Point Location
✍ Raimund Seidel; Udo Adamy πŸ“‚ Article πŸ“… 2000 πŸ› Elsevier Science 🌐 English βš– 241 KB

What is the smallest constant c so that the planar point location queries can be Ž . Ž . answered in c log n q o log n steps i.e., point᎐line comparisons in the worst 2 Ž case? M. T. Goodrich, M. Orletsky, and K. Ramaiyer 1997, in ''Proc 8th ACM-Ž . . SIAM Symp on Discrete Algorithms SODA ,'' pp. 75