Online algorithms for the multiple time series search problem

Online algorithms for the multiple time series search problem

0.00 Avg rating0 Votes
Article ID: iaor20118768
Volume: 39
Issue: 5
Start Page Number: 929
End Page Number: 938
Publication Date: May 2012
Journal: Computers and Operations Research
Authors: , , ,
Keywords: search
Abstract:

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 ] equ1 ( 0 < m < M ) equ2, 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 equ3 goes to infinity. Numerical computation further shows that the gap between the upper and lower bounds first increases and then decreases as M / m equ4 rises.

Reviews

Required fields are marked *. Your email address will not be published.