Optimal Online Algorithms for the Multi-objective Time Series Search Problem
作者： Shun Hasegawa , Toshiya Itoh
DOI: 10.1007/978-3-319-30139-6_24
关键词:
摘要: Tiedemann, et al. [Proc. of WALCOM, LNCS 8973, 2015, pp. 210–221] defined multi-objective online problems and the competitive analysis for problems, presented best possible algorithms with respect to several measures analysis. In this paper, we first point out that frameworks due do not necessarily capture efficiency provide modified definitions problems. Under framework, present a simple algorithm Balanced Price Policy bpp\(_{k}\) time series search problem, show is any measure For derive exact values ratio problem worst component analysis, arithmetic mean geometric
springer.com
harvard.edu
arxiv.org
sci-hub.st 参考文章(11)
Morten Tiedemann, Jonas Ide, Anita Schöbel, Competitive Analysis for Multi-objective Online Algorithms workshop on algorithms and computation. pp. 210- 221 ,(2015) , 10.1007/978-3-319-15612-5_19
Neal E. Young, Online Paging and Caching. Encyclopedia of Algorithms. pp. 1457- 1461 ,(2008)
Ran El-Yaniv, Allan Borodin, Online Computation and Competitive Analysis ,(1998)
Daniel D. Sleator, Robert E. Tarjan, Amortized efficiency of list update and paging rules Communications of The ACM. ,vol. 28, pp. 202- 208 ,(1985) , 10.1145/2786.2793
Esther Mohr, Iftikhar Ahmad, Günter Schmidt, Online algorithms for conversion problems: A survey Surveys in Operations Research and Management Science. ,vol. 19, pp. 87- 104 ,(2014) , 10.1016/J.SORMS.2014.08.001
Elias Koutsoupias, The k-server problem Computer Science Review. ,vol. 3, pp. 105- 118 ,(2009) , 10.1016/J.COSREV.2009.04.002
R. El-Yaniv, A. Fiat, R. M. Karp, G. Turpin, Optimal Search and One-Way Trading Online Algorithms Algorithmica. ,vol. 30, pp. 101- 139 ,(2001) , 10.1007/S00453-001-0003-0
Michael H. Goldwasser, A survey of buffer management policies for packet switches Sigact News. ,vol. 41, pp. 100- 128 ,(2010) , 10.1145/1753171.1753195
Matthias Ehrgott, Multicriteria Optimization ,(2005)
Neal E. Young, Online Paging and Caching Encyclopedia of Algorithms. pp. 601- 604 ,(2008) , 10.1007/978-0-387-30162-4_267