Abstract

Analysis of algorithms with complete knowledge of its inputs is sometimes not up to our expectations. Many times we are surrounded with such scenarios where inputs are generated without any prior knowledge. Online Algorithms have found their applicability in broad areas of computer engineering. Among these, an online financial algorithm is one of the most important areas where lots of efforts have been used to produce an efficient algorithm. In this paper various “Online Algorithms” have been reviewed for their efficiency and various alternative measures have been explored for analysis purposes.

References

• P. Raghavan, A statistical adversary for online algorithms. Online Algorithms, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pp. 79–83, 1991.
• S.al-Binali, The competitive analysis of risk taking with application to online trading. In Proceedings of the 38th Annual IEEE Symposium on Foundations of Computer Science, Miami Beach, Florida, pp. 336–344, 1997.
• R. El-Yaniv, A. Fiat, R. M. Karp, and G. Turpin, Optimal search and one-way trading online algorithms. Algorithmica, pp. 101–139, 2001.
• R.L. Graham, Bounds for certain multiprocessor anomalies. Bell System Technical Journal, 45:1563-1581, 1966.
• D.Sleator and R. E. Tarjan, Amortized efficiency of list update and paging rules. Communications of the ACM, 28:202-208, 1985.
• Ronen I. Brafman, Moshe Tennenholtz, An axiomatic treatment of three qualitative decision criteria. Journal of the ACM (JACM), v.47 n.3, p.452-482, May 2000.
• R. El-Yaniv, A. Fiat, R. Karp, G. Turpin, Competitive analysis of financial games. In Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, pp. 327-333, 1992.
• Ran El-Yaniv, Competitive solutions for online financial problems. ACM Computing Surveys (CSUR), v.30 n.1, p.28-69, March 1998.
• E. Koutsoupias and C. H. Papadimitriou, Beyond competitive analysis. In Proceedings of the Symposium on the Foundation of Computer Science, pp.394-400, 1994.
• Lili Ding, Xinmin Liu, Wanglin Kang, Competitive analysis of online price discount replacement problem. International Joint Conference on Computational Sciences and Optimization, pp.136-139, 24-26 April 2009.
• R. Fleischer, On the bahncard problem. Theoretical Computer Science, 268:161–174, 2001.
• Hiroshi Fujiwara, Kazuo Iwama, Average-case competitive analyses for ski-rental problems. Algorithmica, 42(1):95-107, 2005.
• ZviLotker, Boaz Patt-Shamir, DrorRawitz, Ski rental with two general options. Information Processing Letters, 108(6):365-368, 2008.
• David P. Helmbold, Robert E. Schapire, Yoram Singer, Manfred K. Warmuth, Online portfolio selection using multiplicative updates. International Conference on Machine Learning(ICML), pp.243-251, 1996.
• Allan Borodin, Ran El-Yaniv, and Vincent Gogan, On the competitive theory and practice of portfolio selection. Latin American Symposium on Theoretical Informatics, pp.173-196, 2000.
• Esther Mohr and Gunter Schmidt, Empirical analysis of an online algorithm for multiple trading problems. Communications in Computer and Information Science (CCIS), pp. 293–302, 2008.
• Wouter M. Koolen, Steven de Rooij, Switching investments. 21st International Conference, ALT 2010, pp.239-254, 2010.
• ShahramEsmaeilsabzali and Nancy A. Day, Online pricing for web service providers. In Proceedings of the international workshop on Economics driven software engineering research (EDSER '06), New York, USA, 37-42, 2006.
• Peter DeMarzo, Ilan Kremer, and Yishay Mansour, Online trading algorithms and robust option pricing. In Proceedings of the 38th annual ACM symposium on Theory of computing (STOC '06). New York, USA, 477-486, 2006.
• Lorenz, Julian Panagiotou, Konstantinos Steger, Angelika, Optimal algorithms for k-search with application in option pricing. Algorithmica, 55(2):311-328, 2009.
• AmitabhaBagchi , Amitabh Chaudhary , Rahul Garg , Michael T. Goodrich , Vijay Kumar, Seller-focused algorithms for online auctioning. Proceedings of the 7th International Workshop on Algorithms and Data Structures, p.135-147, August 08-10, 2001.
• Ziv Bar-Yossef, Kirsten Hildrum, and Felix Wu, Incentive-compatible online auctions for digital goods. In Proceedings of the thirteenth annual ACM-SIAM symposium on discrete algorithms (SODA '02), Philadelphia, USA, 964-970, 2002.
• Avrim Blum, Jason D. Hartline, Near-optimal online auctions. In Proceedings of the Sixteenth Annual ACM-SIAM symposium on Discrete algorithms (SODA '05), Vancouver, BC, Canada, 1156-1163, 2005.
• Avrim Blum, TuomasSandholm, Martin Zinkevich, Online algorithms for market clearing. Journal of the ACM (JACM) Vol.53:845-879, 2006.
• Amos Fiat, Gerhard J. Woeginger, Competitive analysis of algorithms. Online Algorithms: The State of the Art, Springer, 1998.