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

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.

	PDF - Published Version Restricted to Registered users only Download (2MB) | Request a copy
Preview	PDF (SCOPUS) - Supplemental Material Download (165kB) | Preview
Preview	PDF (WOS) - Supplemental Material Download (270kB) | Preview

Abstract

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.

Item Type:	Conference or Workshop Item (Plenary Papers)
Additional Information:	6566/68536
Uncontrolled Keywords:	competitive analysis, Online algorithms
Subjects:	T Technology > T Technology (General) > T10.5 Communication of technical information
Kulliyyahs/Centres/Divisions/Institutes (Can select more than one option. Press CONTROL button):	Kulliyyah of Information and Communication Technology Kulliyyah of Information and Communication Technology Kulliyyah of Information and Communication Technology > Department of Information System Kulliyyah of Information and Communication Technology > Department of Information System
Depositing User:	Prof Asadullah Shah
Date Deposited:	28 Dec 2018 15:43
Last Modified:	13 Jun 2019 11:22
URI:	http://irep.iium.edu.my/id/eprint/68536

Actions (login required)

View Item