On the Competitive Analysis for the Multi-Objective Time Series Search Problem
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:Rk→R. 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.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E102-A No.9 pp.1150-1158
- Publication Date
- 2019/09/01
- Publicized
- 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
Authors
Toshiya ITOH
Tokyo Institute of Technology
Yoshinori TAKEI
Akita College
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Toshiya ITOH, Yoshinori TAKEI, "On the Competitive Analysis for the Multi-Objective Time Series Search Problem" in IEICE TRANSACTIONS on Fundamentals,
vol. E102-A, no. 9, pp. 1150-1158, September 2019, doi: 10.1587/transfun.E102.A.1150.
Abstract: 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:Rk→R. 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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E102.A.1150/_p
Copy
@ARTICLE{e102-a_9_1150,
author={Toshiya ITOH, Yoshinori TAKEI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={On the Competitive Analysis for the Multi-Objective Time Series Search Problem},
year={2019},
volume={E102-A},
number={9},
pages={1150-1158},
abstract={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:Rk→R. 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.},
keywords={},
doi={10.1587/transfun.E102.A.1150},
ISSN={1745-1337},
month={September},}
Copy
TY - JOUR
TI - On the Competitive Analysis for the Multi-Objective Time Series Search Problem
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1150
EP - 1158
AU - Toshiya ITOH
AU - Yoshinori TAKEI
PY - 2019
DO - 10.1587/transfun.E102.A.1150
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E102-A
IS - 9
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - September 2019
AB - 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:Rk→R. 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.
ER -
English
