Competitive Algorithms for Online Conversion Problem with Interrelated Prices

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.

@article{Iqbal2019,
  title     = {Competitive Algorithms for Online Conversion Problem with Interrelated Prices},
  journal   = {International Journal of Advanced Computer Science and Applications},
  volume    = {10},
  number    = {6},
  year      = {2019},
  publisher = {The Science and Information Organization},
  author    = {Javeria Iqbal and Iftikhar Ahmad and Asadullah Shah},
  doi       = {10.14569/IJACSA.2019.0100675},
  url       = {https://doi.org/10.14569/IJACSA.2019.0100675}
}