Competitive Algorithms for Online Conversion Problem with Interrelated Prices
Journal Title: International Journal of Advanced Computer Science & Applications - Year 2019, Vol 10, Issue 6
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 derive a lower bound on the competitive ratio of randomized non-preemptive 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 reservation 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.
Authors and Affiliations
Javeria Iqbal, Iftikhar Ahmad, Asadullah Shah
Keywords
Related Articles
- EP ID EP597493
- DOI 10.14569/IJACSA.2019.0100675
- Views 71
- Downloads 0
A Novel Method for Measuring the Performance of Software Project Managers
This paper is focused on providing a novel method for measuring the performance of software project managers. It clarifies the fundamental concepts of software project management, knowledge areas, life cycle phases of so...
Survey on Impact of Software Metrics on Software Quality
Software metrics provide a quantitative basis for planning and predicting software development processes. Therefore the quality of software can be controlled and improved easily. Quality in fact aids higher product...
Multidimensional Neural-Like Growing Networks - A New Type of Neural Network
The present paper describes a new type of neural networks - multidimensional neural-like growing networks. Multidimensional neural-like growing networks are a dynamic structure, which varies depending on the external inf...
An Information Hiding Scheme Based on Pixel-Value-Ordering and Prediction-Error Expansion with Reversibility
This paper proposes a data hiding scheme based on pixel-value-ordering and predication-error expansion. In a natural image, most neighboring pixels have similar pixel values, i.e. the difference between neighboring pixel...
Secret Key Agreement Over Multipath Channels Exploiting a Variable-Directional Antenna
We develop an approach of key distribution protocol(KDP) proposed recently by T.Aono et al., where the security of KDP is only partly estimated in terms of eavesdropper's key bit errors. Instead we calculate the S...