Volume 20, No 6, 2013, P. 16-29
Velikanova Yu. Yu.
The online algorithms for the problem of finding the maximum of the unimodal function
We consider an online problem of auto-focusing of a camera. The sharpness function is smooth and it has the only maximum on the interval. The values of the function are unknown. We have a measuring device that can move to any point of the interval and compute the value of the sharpness function in this point. The measuring device spends energy for moving to the point and computing the value. We need to localize the maximum of the sharpness function in the ε-interval so as to minimize the energy consumption. Two algorithms, Golden Section Search and Dichotomy, are considered. We also present three new algorithms for solving this problem. For these algorithms, we study their worst and best case ratios.
Keywords: online problem, online algorithm, minimization of energy.
Velikanova Yuliya Yurevna 1,2
1. S. L. Sobolev Institute of Mathematics, SB RAS,
4 Acad. Koptyug Ave., 630090 Novosibirsk, Russia
Novosibirsk State University,
2 Pirogov St., 630090 Novosibirsk, Russia