Optimal algorithms for online time series search and one-way trading with interrelated prices |
| |
Authors: | Wenming Zhang Yinfeng Xu Feifeng Zheng Yucheng Dong |
| |
Institution: | 1. School of Management, Xi??an JiaoTong University, Xi??an, 710049, China 2. State Key Lab for Manufacturing Systems Engineering, Xi??an, 710049, China
|
| |
Abstract: | 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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|