On the deterministic complexity of searching local maxima

DOI10.1016/0166-218X(93)90002-6MaRDI QIDQ1801675zbMATH OpenOpenAlexFDO

Authors Ingo Althöfer, Klaus-Uwe Koschnick

Publication date 17 August 1993

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0166-218x(93)90002-6

zbMATH Keywords

boundsdeterministic complexitygridslocal maxima

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• scientific article; zbMATH DE number 1962814
• On the complexity of finding a local maximum of functions on discrete planar subsets
• On the complexity of the search of an extremum of a function
• On the query complexity of finding a local maximum point.
• On the quantum query complexity of local search in two and three dimensions

Cites work

• Edge-isoperimetric inequalities in the grid
• Local optimization on graphs

Cited in

(10)

• Condition number based complexity estimate for computing local extrema
• Dividing and conquering the square
• On the query complexity of finding a local maximum point.
• The query complexity of finding local minima in the lattice
• On the complexity of finding a local maximum of functions on discrete planar subsets
• Query complexity of approximate equilibria in anonymous games
• Optimal Randomized Algorithms for Local Sorting and Set-Maxima
• scientific article; zbMATH DE number 1962814 (Why is no real title available?)
• Local Search for Max-Sum Diversification
• Search for the maximum of a random walk

This page was built for publication: On the deterministic complexity of searching local maxima

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