Skip to main content

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.

search-config
loading …

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)

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Metadaten
Titel
Erratum: Competitive Analysis for Multi-Objective Online Algorithms
verfasst von
Morten Tiedemann
Jonas Ide
Anita Schöbel
Copyright-Jahr
2015
Verlag
Springer International Publishing
DOI
https://doi.org/10.1007/978-3-319-15612-5_31