テクニカルレポート Optimal Online Algorithms for the Multi-Objective Time Series Search Problem

長谷川, 駿  ,  Hasegawa, Shun  ,  伊東, 利哉  ,  Itoh, Toshiya

2015-06
内容記述
Tiedemann, et al. [Proc. of WALCOM, LNCS 8973, 2015, pp.210-221] defined multi-objective online problems and the competitive analysis for multi-objective online problems and showed that (1) with respect to the worst component competitive analysis, the online algorithm reservation price policy RPP-HIGH is best possible for the multi-objective time series search problem,(2) with respect to the arithmetic mean component competitive analysis, theonline algorithm RPP-MULT is best possible for the bi-objective time seriessearch problem; (3) with respect to the geometric mean component competitiveanalysis, the online algorithm RPP-MULT is best possible for the bi-objectivetime series search problem. In this paper, we present a simple~online algorithm Balanced Price Policy $BPP_{k}$ for the multi-objective ($k$-objective) time series search problem, and show that the algorithm $BPP_{k}$ is best possible with respect to any measure of the competitive analysis. In addition, we derive exact values of the competitive ratio for the multi-objective time series search problem with respect to the worst component, the arithmetic mean component, and the geometric mean component competitive analysis.

このアイテムのアクセス数:  回

その他の情報