Closed Formulas of the Arithmetic Mean Component Competitive Ratio for the 3-Objective and 4-Objective Time Series Search Problems

12/01/2017
by   Toshiya Itoh, et al.
0

For the multi-objective time series search problem, Hasegawa and Itoh [Proc. of WALCOM, LNCS 9627, 2016, pp.201-212] presented the best possible online algorithm balanced price policy BPP for any monotone function f: R^k → R and derived the exact values of the competitive ratio for several monotone functions. Specifically for the monotone function f(c_1,...,c_k)=(c_1,...,c_k)/k, Hasegawa and Itoh derived the exact value of the arithmetic mean component competitive ratio for k=2 but it is not known for any integer k ≥ 3. In this paper, we derive the exact values of the arithmetic mean component competitive ratio for k=3 and k=4.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset