Online algorithms for the multiple time series search problem

This work investigates the online multiple time series search problem. Given a storage with finite capability, a player receives one product for sale and observes a selling price as well at each period. With the knowledge that prices in all periods vary within [m,M] (0<m<M), the player decides at the period whether to sell some of the products in the storage together with the one currently received at the price observed or to store the current one in the storage. Our main contributions are three online algorithms TRPP, SOEP and TS where TS is a combination of TRPP and SOEP, and their competitiveness analyses. Moreover, we prove a lower bound of the competitive ratio for the problem, and prove that TS is optimal as the ratio M/m goes to infinity. Numerical computation further shows that the gap between the upper and lower bounds first increases and then decreases as M/m rises.