On the complexity of finding a local maximum of functions on discrete planar subsets
| Autor: | Anton Mityagin |
|---|---|
| Rok vydání: | 2004 |
| Předmět: |
General Computer Science
Computational complexity theory Plane (geometry) Decision trees Function (mathematics) Upper and lower bounds Domain (mathematical analysis) Theoretical Computer Science Discrete system Combinatorics Computational complexity Integer Local maximum search Local search (constraint satisfaction) Mathematics Computer Science(all) |
| Zdroj: | Theoretical Computer Science. 310(1-3):355-363 |
| ISSN: | 0304-3975 |
| DOI: | 10.1016/s0304-3975(03)00426-2 |
| Popis: | We study how many values of an unknown integer-valued function f one needs to know in order to find a local maximum of f. We consider functions defined on finite subsets of discrete plane. We prove upper bounds for functions defined on rectangles and present lower bounds for functions defined on arbitrary domains in terms of the size of the domain and the size of its border. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect