Competitive algorithms for online conversion problems 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...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English English |
| Published: |
The Science and Information (SAI) Organization Limited
2019
|
| Subjects: | |
| Online Access: | http://irep.iium.edu.my/74100/ http://irep.iium.edu.my/74100/ http://irep.iium.edu.my/74100/ http://irep.iium.edu.my/74100/7/74100%20Competitive%20Algorithms%20for%20Online%20Conversion.pdf http://irep.iium.edu.my/74100/8/74100%20Competitive%20Algorithms%20for%20Online%20Conversion%20SCOPUS.pdf |
| Summary: | 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. |
|---|