Analysis of threat based algorithm using different performance measures
RAIRO. Operations Research, Tome 55 (2021), pp. S2393-S2401

Since its introduction in 1985, competitive analysis is a widely used tool for the performance measurement of online algorithms. Despite its simplicity and popularity, competitive analysis has its own set of drawbacks which lead to the development of other performance measures. However, these measures were seldom applied to problems in other domains. Recently Boyar et al. (Theor. Comput. Sci. 532 (2014) 2–13) studied the online search problem using various performance analysis measures for non-preemptive algorithms. We extend the work by considering preemptive threat-based algorithms and evaluate it using competitive analysis, bijective analysis, average case and relative interval analysis. For competitive analysis, and average case analysis, our findings are in contrast with that of Boyar et al., whereas for bijective and relative interval analysis our findings complement that of Boyar et al.

DOI : 10.1051/ro/2020092
Classification : 90C27
Keywords: Online conversion problem, online algorithms, competitive analysis 
@article{RO_2021__55_S1_S2393_0,
     author = {Ahmad, Iftikhar and Pirron, Marcus and Schmidt, G\"unter},
     title = {Analysis of threat based algorithm using different performance measures},
     journal = {RAIRO. Operations Research},
     pages = {S2393--S2401},
     year = {2021},
     publisher = {EDP-Sciences},
     volume = {55},
     doi = {10.1051/ro/2020092},
     mrnumber = {4223077},
     zbl = {1472.90105},
     language = {en},
     url = {https://www.numdam.org/articles/10.1051/ro/2020092/}
}
TY  - JOUR
AU  - Ahmad, Iftikhar
AU  - Pirron, Marcus
AU  - Schmidt, Günter
TI  - Analysis of threat based algorithm using different performance measures
JO  - RAIRO. Operations Research
PY  - 2021
SP  - S2393
EP  - S2401
VL  - 55
PB  - EDP-Sciences
UR  - https://www.numdam.org/articles/10.1051/ro/2020092/
DO  - 10.1051/ro/2020092
LA  - en
ID  - RO_2021__55_S1_S2393_0
ER  - 
%0 Journal Article
%A Ahmad, Iftikhar
%A Pirron, Marcus
%A Schmidt, Günter
%T Analysis of threat based algorithm using different performance measures
%J RAIRO. Operations Research
%D 2021
%P S2393-S2401
%V 55
%I EDP-Sciences
%U https://www.numdam.org/articles/10.1051/ro/2020092/
%R 10.1051/ro/2020092
%G en
%F RO_2021__55_S1_S2393_0
Ahmad, Iftikhar; Pirron, Marcus; Schmidt, Günter. Analysis of threat based algorithm using different performance measures. RAIRO. Operations Research, Tome 55 (2021), pp. S2393-S2401. doi: 10.1051/ro/2020092

[1] I. Ahmad, M. I. K. Khalil and S. A. A. Shah, Optimization-based workload distribution in geographically distributed data centers: a survey. Int. J. Commun. Syst. 33 (2020) e4453. | DOI

[2] S. Albers, Online algorithms: a survey. Math. Prog. 97 (2003) 3–26. | MR | Zbl | DOI

[3] S. Angelopoulos and P. Schweitzer, Paging and list update under bijective analysis. J. ACM 60 (2013) 7:1–7:18. | MR | Zbl | DOI

[4] S. Angelopoulos, R. Dorrigiv and A. López-Ortiz, On the separation and equivalence of paging strategies. In: Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms. SODA ’07. Society for Industrial and Applied Mathematics. Philadelphia, PA (2007) 229–237. | MR | Zbl

[5] J. Boyar, K. S. Larsen and A. Maiti, A comparison of performance measures via online search. Theor. Comput. Sci. 532 (2014) 2–13. | MR | Zbl | DOI

[6] R. Dorrigiv, A. López-Ortiz and J. Ian Munro, On the relative dominance of paging algorithms. Theor. Comput. Sci. 410 (2009) 3694–3701. | MR | Zbl | DOI

[7] R. El-Yaniv, A. Fiat, R. M. Karp and G. Turpin, Competitive analysis of financial games. In: IEEE Symposium on Foundations of Computer Science, Manhattan, NY (1992) 327–333. | Zbl

[8] R. El-Yaniv, A. Fiat, R. M. Karp and G. Turpin, Optimal search and one-way trading online algorithms. Algorithmica 30 (2001) 101–139. | MR | Zbl | DOI

[9] H. Fujiwara, K. Iwama and Y. Sekiguchi, Average-case competitive analyses for one-way trading. J. Comb. Optim. 21 (2011) 83–107. | MR | Zbl | DOI

[10] J. Iqbal and I. Ahmad, Optimal online k -min search. EURO J. Comput. Optim. 3 (2015) 147–160. | MR | Zbl | DOI

[11] J. Iqbal, I. Ahmad and A. Shah, Disparity between theory & practice: Beyond the worst-case competitive analysis. In: 2018 IEEE 5th International Conference on Engineering Technologies and Applied Sciences (ICETAS). IEEE, Manhattan, NY (2018) 1–6.

[12] E. Mohr, I. Ahmad and G. Schmidt, Online algorithms for conversion problems: a survey. Surv. Oper. Res. Manage. Sci. 19 (2014) 87–104. | MR

[13] D. Sleator and R. Tarjan, Amortized efficiency of list update and paging rules. Commun. ACM 28 (1985) 202–208. | MR | DOI

[14] N. Young, The k -server dual and loose competitiveness for paging. Algorithmica 11 (1994) 525–541. | MR | DOI

Cité par Sources :