On the query complexity of finding a local maximum point. (English) Zbl 1042.68054
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.
MSC:
| 68Q25 | Analysis of algorithms and problem complexity |
References:
| [1] | Avriel, M.; Wilde, D., Optimality proof for the symmetric Fibonacci search technique, The Fibonacci Quarterly, 4, 265-269 (1966) · Zbl 0144.40705 |
| [2] | Beklemishev, L. D., A proof-theoretic analysis of collection, Arch. Math. Logic, 37, 275-296 (1998) · Zbl 0916.03038 |
| [3] | Beklemishev, L. D., On the induction schema for decidable predicates, (Logic Group Preprint Series (2000), Department of Philosophy, Utrecht University), To appear in J. Symbolic Logic · Zbl 1041.03042 |
| [4] | Crescenzi, P.; Silvestri, R., Sperner’s lemma and robust machines, (8th Annual Structure in Complexity Theory Conference, May 18-21, 1993 (1993)), 194-199 · Zbl 1034.68519 |
| [5] | Gasarch, W., Bounded Queries in Recursion Theory (1999), Birkhäuser: Birkhäuser Basel · Zbl 0936.03038 |
| [6] | Kiefer, J., Sequential minimax search for a maximum, Proc. Amer. Math. Soc., 4, 502-506 (1953) · Zbl 0050.35702 |
| [7] | Knuth, D. E., The Art of Computer Programming, Vols. I, II (1968), Addison-Wesley: Addison-Wesley Reading, MA, 3rd ed.: 1998 · Zbl 0191.17903 |
| [8] | Lovasz, L.; Naor, M.; Newman, I.; Wigderson, A., Search problems in the decision tree model, (32th FoCS (1991)), 576-585 |
| [9] | A. Mitiaguine, Personal communication, Spring 2001; A. Mitiaguine, Personal communication, Spring 2001 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
