On the query complexity of finding a local maximum point.

DOI10.1016/S0020-0190(02)00313-7MaRDI QIDQ1853165zbMATH OpenOpenAlexFDO

Authors A. L. Rastsvetaev, Lev D. Beklemishev

Publication date 21 January 2003

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0020-0190(02)00313-7, https://dspace.library.uu.nl/handle/1874/27013

zbMATH Keywords

Computational complexityDecision treesFibonacci numbersLocal maximum search

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Review text

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\geqslant1\). Matching upper and lower bounds are obtained. The bounds are formulated in terms of certain Fibonacci type sequences of numbers.

Recommendations

• On the deterministic complexity of searching local maxima
• scientific article; zbMATH DE number 1962814
• On the complexity of finding a local maximum of functions on discrete planar subsets
• The query complexity of finding local minima in the lattice
• Local search: complexity and approximation
• On the complexity of finding a local minimizer of a quadratic function over a polytope
• scientific article; zbMATH DE number 1884459
• On the complexity of the search of an extremum of a function
• Polynomial time \(\rho\)-locally maximum volume search
• A note on the complexity of local search problems

Cites work

• A proof-theoretic analysis of collection
• Bounded queries in recursion theory
• scientific article; zbMATH DE number 3233290 (Why is no real title available?)
• scientific article; zbMATH DE number 3303654 (Why is no real title available?)
• On the induction schema for decidable predicates
• Sequential Minimax Search for a Maximum
• Sperner's lemma and robust machines

Cited in

(7)

• Operations research applications of dichotomous search
• On the deterministic complexity of searching local maxima
• Dividing and conquering the square
• The query complexity of finding local minima in the lattice
• On the complexity of finding a local maximum of functions on discrete planar subsets
• On the complexity of searching for a maximum of a function on a quantum computer
• scientific article; zbMATH DE number 1962814 (Why is no real title available?)

This page was built for publication: On the query complexity of finding a local maximum point.

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