Competitive algorithms for online conversion problems with interrelated prices

Iqbal, Javeria and Ahmad, Iftikhar and Shah, Asadullah (2019) Competitive algorithms for online conversion problems with interrelated prices. International Journal of Advanced Computer Science and Applications (IJACSA), 10 (6). pp. 582-589. ISSN 2158-107X E-ISSN 2156-5570

	PDF - Published Version Restricted to Registered users only Download (450kB) | Request a copy
	PDF (SCOPUS) - Supplemental Material Restricted to Registered users only Download (620kB) | Request a copy
Preview	PDF (wos) - Supplemental Material Download (332kB) | Preview

Abstract

The classical uni-directional conversion algorithms are based on the assumption that prices are arbitrarily chosen from the fixed price interval[m, M] where m and M represent the estimated lower and upper bounds of possible prices 0<m<M. The estimated interval is erroneous and no attempts are made by the algorithms to update the erroneous estimates. We consider a real world setting where prices are interrelated, i.e., each price depends on its preceding price. Under this assumption, we drive a lower bound on the competitive ratio of randomized non-primitive algorithms. Motivated by the fixed and erroneous price bounds, we present an update model that progressively improves the bounds. Based on the update model, we propose a non-preemptive reservations price algorithm RP* and analyze it under competitive analysis. Finally, we report the findings of an experimental study that is conducted over the real world stock index data. We observe that RP* consistently outperforms the classical algorithm.

Item Type:	Article (Journal)
Additional Information:	6566/74100
Uncontrolled Keywords:	Time series search; one-way trading; online algorithms; update model
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 > Department of Information System Kulliyyah of Information and Communication Technology > Department of Information System Kulliyyah of Information and Communication Technology Kulliyyah of Information and Communication Technology
Depositing User:	Prof Asadullah Shah
Date Deposited:	13 Sep 2019 10:16
Last Modified:	12 Apr 2020 23:40
URI:	http://irep.iium.edu.my/id/eprint/74100

Actions (login required)

View Item