Optimal algorithms for online time series search and one-way trading with interrelated prices

The basic models of online time series search and one-way trading are introduced by El-Yaniv et al. in Algorithmica 30(1), 101-139 (2001) where it is assumed that the prices are bounded within interval [m,M] (0<m<M). In this paper, we consider another case where every two consecutive prices are interrelated, that is, the variation range of each price depends on its preceding price. We present optimal deterministic online algorithms for the two problems, respectively. According to one conclusion in Algorithmica 30(1), 101-139 (2001), we further point out that for the case we considered, an optimal deterministic algorithm for the one-way trading problem can be regarded as an optimal randomized one for the time series search problem, and randomization is useless for the one-way trading problem.