On the Competitive Analysis for the Multi-Objective Time Series Search Problem

Toshiya ITOH  Yoshinori TAKEI  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E102-A   No.9   pp.1150-1158
Publication Date: 2019/09/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E102.A.1150
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: Optimization
Keyword: 
multi-objective time series search problem,  monotone functions,  arithmetic mean component competitive ratio,  

Full Text: PDF(869.2KB)>>
Buy this Article




Summary: 
For the multi-objective time series search problem, Hasegawa and Itoh [Theoretical Computer Science, Vol.78, pp.58-66, 2018] presented the best possible online algorithm balanced price policy for any monotone function f:RkR. Specifically the competitive ratio with respect to the monotone function f(c1,...,ck)=(c1+…+ck)/k is referred to as the arithmetic mean component competitive ratio. Hasegawa and Itoh derived the explicit representation of the arithmetic mean component competitive ratio for k=2, but it has not been known for any integer k≥3. In this paper, we derive the explicit representations of the arithmetic mean component competitive ratio for k=3 and k=4, respectively. On the other hand, we show that it is computationally difficult to derive the explicit representation of the arithmetic mean component competitive ratio for arbitrary integer k in a way similar to the cases for k=2, 3, and 4.