On the complexity of finding a local max
โ
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