Disparity between theory & practice beyond the worst-case competitive analysis

Online algorithms are used in a variety of situations such as forex trading, cache replacement, and job scheduling etc. In an online problem, the algorithms is presented with a sequence on input in a serial fashion such that the algorithm does not have knowledge about the future inputs. For instance...

Full description

Bibliographic Details
Main Authors:	Iqbal, Javeria, Ahmad, Iftikhar, Shah, Asadullah
Format:	Conference or Workshop Item
Language:	English English English
Published:	Institute of Electrical and Electronics Engineers Inc. 2019
Subjects:	T10.5 Communication of technical information
Online Access:	http://irep.iium.edu.my/68536/ http://irep.iium.edu.my/68536/ http://irep.iium.edu.my/68536/ http://irep.iium.edu.my/68536/1/68536_Disparity%20between%20theory%20%26%20practice.pdf http://irep.iium.edu.my/68536/2/68536_Disparity%20between%20theory%20%26%20practice_SCOPUS.pdf http://irep.iium.edu.my/68536/3/68536_Disparity%20between%20theory%20%26%20practice_WOS.pdf

id	iium-68536
recordtype	eprints
spelling	iium-685362019-06-13T03:22:15Z http://irep.iium.edu.my/68536/ Disparity between theory & practice beyond the worst-case competitive analysis Iqbal, Javeria Ahmad, Iftikhar Shah, Asadullah T10.5 Communication of technical information Online algorithms are used in a variety of situations such as forex trading, cache replacement, and job scheduling etc. In an online problem, the algorithms is presented with a sequence on input in a serial fashion such that the algorithm does not have knowledge about the future inputs. For instance, in case of forex, the online algorithm is presented daily exchange rates. The algorithm does not have knowledge about future exchange rates, and has to make an irreversible conversion decision on each day. Competitive analysis is the standard tool to analyse the performance of online algorithms. Competitive analysis measures the performance of an online algorithm against a benchmark optimum offline algorithm. Competitive analysis is a worst case measure and is criticized as a pessimistic approach for performance evaluation. The assumption of online algorithms designed under the competitive analysis paradigm also suffer from the same set of problems as competitive analysis itself. In this work, we contribute towards bridging the gap between theory and practice by considering a set of algorithms for online conversion problems and discuss the disparity between the assumed worst case competitive rations and experimentally achieved competitive ratios using real world data. We present modified worst-case input sequences in order to make them comparable to real world data. In addition, we also investigate, how the assumptions made by the algorithm differs from real world. Further, we highlight other performance measures for online algorithms with the goal of realistic performance evaluation process. Institute of Electrical and Electronics Engineers Inc. 2019-01-28 Conference or Workshop Item PeerReviewed application/pdf en http://irep.iium.edu.my/68536/1/68536_Disparity%20between%20theory%20%26%20practice.pdf application/pdf en http://irep.iium.edu.my/68536/2/68536_Disparity%20between%20theory%20%26%20practice_SCOPUS.pdf application/pdf en http://irep.iium.edu.my/68536/3/68536_Disparity%20between%20theory%20%26%20practice_WOS.pdf Iqbal, Javeria and Ahmad, Iftikhar and Shah, Asadullah (2019) Disparity between theory & practice beyond the worst-case competitive analysis. In: 5th IEEE International Conference on Engineering Technologies and Applied Sciences (ICETAS) 2018, 22nd-23rd Nov. 2018, Bangkok, Thailand. https://ieeexplore.ieee.org/document/8629111 10.1109/ICETAS.2018.8629111
repository_type	Digital Repository
institution_category	Local University
institution	International Islamic University Malaysia
building	IIUM Repository
collection	Online Access
language	English English English
topic	T10.5 Communication of technical information
spellingShingle	T10.5 Communication of technical information Iqbal, Javeria Ahmad, Iftikhar Shah, Asadullah Disparity between theory & practice beyond the worst-case competitive analysis
description	Online algorithms are used in a variety of situations such as forex trading, cache replacement, and job scheduling etc. In an online problem, the algorithms is presented with a sequence on input in a serial fashion such that the algorithm does not have knowledge about the future inputs. For instance, in case of forex, the online algorithm is presented daily exchange rates. The algorithm does not have knowledge about future exchange rates, and has to make an irreversible conversion decision on each day. Competitive analysis is the standard tool to analyse the performance of online algorithms. Competitive analysis measures the performance of an online algorithm against a benchmark optimum offline algorithm. Competitive analysis is a worst case measure and is criticized as a pessimistic approach for performance evaluation. The assumption of online algorithms designed under the competitive analysis paradigm also suffer from the same set of problems as competitive analysis itself. In this work, we contribute towards bridging the gap between theory and practice by considering a set of algorithms for online conversion problems and discuss the disparity between the assumed worst case competitive rations and experimentally achieved competitive ratios using real world data. We present modified worst-case input sequences in order to make them comparable to real world data. In addition, we also investigate, how the assumptions made by the algorithm differs from real world. Further, we highlight other performance measures for online algorithms with the goal of realistic performance evaluation process.
format	Conference or Workshop Item
author	Iqbal, Javeria Ahmad, Iftikhar Shah, Asadullah
author_facet	Iqbal, Javeria Ahmad, Iftikhar Shah, Asadullah
author_sort	Iqbal, Javeria
title	Disparity between theory & practice beyond the worst-case competitive analysis
title_short	Disparity between theory & practice beyond the worst-case competitive analysis
title_full	Disparity between theory & practice beyond the worst-case competitive analysis
title_fullStr	Disparity between theory & practice beyond the worst-case competitive analysis
title_full_unstemmed	Disparity between theory & practice beyond the worst-case competitive analysis
title_sort	disparity between theory & practice beyond the worst-case competitive analysis
publisher	Institute of Electrical and Electronics Engineers Inc.
publishDate	2019
url	http://irep.iium.edu.my/68536/ http://irep.iium.edu.my/68536/ http://irep.iium.edu.my/68536/ http://irep.iium.edu.my/68536/1/68536_Disparity%20between%20theory%20%26%20practice.pdf http://irep.iium.edu.my/68536/2/68536_Disparity%20between%20theory%20%26%20practice_SCOPUS.pdf http://irep.iium.edu.my/68536/3/68536_Disparity%20between%20theory%20%26%20practice_WOS.pdf
first_indexed	2023-09-18T21:37:16Z
last_indexed	2023-09-18T21:37:16Z
_version_	1777412903919419392

Disparity between theory & practice beyond the worst-case competitive analysis

Similar Items