Erratum: Competitive Analysis for Multi-Objective Online Algorithms

We identify an error in the analysis of the online algorithm $\textsc{rpp-mult}$ for the bi-objective time series search problem presented in [1]. The strong competitive ratio with respect to $f_2(c) = \frac{1}{k} \sum_{i=1}^k c_i$ of $\textsc{rpp-mult}$ stated in [1, Theorem 3] does not hold due to an error in the proof. In the following, we point out this error. For details about the problem and the terminology, we refer to the original paper.In the course of the proof of [1, Theorem 3], the expression$$\max_{x \in \mathcal{I}_1} \left\{\frac{M_1}{x} + \frac{M_2x}{z^{\star}} \right\}$$is considered (see Equation (9)). Here, the maximum is falsely determined as $x^*= \sqrt{{(M_1z^{\star})}{M_2}}$. In fact, $x^* \notin \mathcal{I}_1$, and, thus, Equation (9) does not hold. The same mistake has been made in Equation (11), i.e., the chosen maximum is not a point in $\mathcal{I}_2$.Note that the proof cannot be modified such that the stated competitive ratio is proven. However, in [2], a best possible algorithm for the bi-objective time series search problem is presented, as outlined below.Hasegawa and Itoh define the online algorithm Balanced Price Policybpp _k for the k-objective time series search problem with respect to an arbitrary monotone continuous function f: ℝk → ℝ, see Algorithm 1.Let $z_k^f = \sup_{\left(x_1,\dots,x_k\right) \in \mathcal{S}_f^k} f\left(\frac{M_1}{x_1},\dots,\frac{M_k}{x_k}\right)$, where$\mathcal{S}_f^k = \left\{ (x_1,\dots,x_k) \in I_1 \times \cdots \times I_k: f\left(\frac{M_1}{x_1},\dots,\frac{M_k}{x_k}\right) = f\left(\frac{x_1}{m_1},\dots,\frac{x_k}{m_k}\right)\right\}$with I _i  = [m _i ,M _i ] for i = 1,…,k.Hasegawa and Itoh prove that, for any integer k ≥ 1 and any monotone continuous function f: ℝk → ℝ, the competitive ratio of $\textsc{bpp}_k$ with respect to f is given by $z_f^k$ and this is the best possible competitive ratio, see [2, Section 4.1].By means of this result, the following theorem gives the best possible competitive ratio with respect to f₂ and k = 2:Theorem 1 (Hasegawa and Itoh, [2, Theorem 6.1]).With respect to the function f₂ for k = 2, the following holds:$z^2_{f_2} = \frac{1}{2}\left\lbrack \sqrt{\left(\frac{1}{2}\left(\frac{M_2}{m_2}-1\right)\right)^2 + \frac{M_1}{m_1}} + \frac{1}{2}\left(\frac{M_2}{m_2}+1\right) \right \rbrack.$References1Tiedemann, M. and Ide, J. and Schöbel, A.: Competitive Analysis for Multi-Objective Online Algorithms. In: Proceedings of the 9th Workshop on Algorithms and Computation (WALCOM). LNCS, vol. 8973, pp. 210–221 (2015)2Hasegawa, S. and Itoh, T.: Optimal Online Algorithms for the Multi-Objective Time Series Search Problem. arXiv:1506.04474v4 [cs.DS] (2015)