2015 | Erratum | Buchkapitel
Erratum: Competitive Analysis for Multi-Objective Online Algorithms
verfasst von : Morten Tiedemann, Jonas Ide, Anita Schöbel
Erschienen in: WALCOM: Algorithms and Computation
Verlag: Springer International Publishing
Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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 f2 and k = 2:Theorem 1 (Hasegawa and Itoh, [2, Theorem 6.1]).With respect to the function f2 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)