Skip to main content
SpringerLink
Log in

On the on-line rent-or-buy problem in probabilistic environments

  • Original Article
  • Published:
Journal of Global Optimization Aims and scope Submit manuscript

Abstract

Fujiwara and Iwama [In: The 13th Annual International Symposium on Algorithms and Computation, pp. 476–488 (2002)] first integrated probability distribution into the classical competitive analysis to study the rental problem. They assumed that the future inputs are drawn from an exponential distribution, and obtained the optimal competitive strategy and the competitive ratio by the derivative method. In this paper, we introduce the interest rate and tax rate into the continuous model of Fujiwra and Iwama [In: The 13th Annual International Symposium on Algorithms and Computation, pp. 476–488 (2002)]. Moreover, we use the forward difference method in different probabilistic environments to consider discrete leasing models both with and without the interest rate. We not only give the optimal competitive strategies and their competitive ratios in theory, but also give numerical results. We find that with the introduction of the interest rate and tax rate, the uncertainty involved in the process of decision making will diminish and the optimal purchasing date will be put off.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Similar content being viewed by others

References

  1. Albers S., Charikar M., Mitzenmacher M. (2001) On delayed information and action in on-line algorithms. Inf. Comput. 170, 135–152

    Article  Google Scholar 

  2. al-Binali S. (1999) A risk–reward framework for the competitive analysis of financial games. Algorithmica 25, 99–115

    Article  Google Scholar 

  3. Azar Y., Bartal Y., Feuerstein E., Fiat A., Leonardi S., Rosén A. (1999) On capital investment. Algorithmica 25, 22–36

    Article  Google Scholar 

  4. Ben-David S., Borodin A., Karp R.M., Tardos G., Wigderson A. (1994) On the power of randomization in on-line algorithms. Algorithmica 11, 2–14

    Article  Google Scholar 

  5. Borodin A., El-Yaniv R. (1998) On-line Computation and Competitive Analysis. Cambridge University Press, Cambridge

    Google Scholar 

  6. Damaschke P. (2003) Nearly optimal strategies for special cases of on-line capital investment. Theor. Comput. Sci. 302, 35–44

    Article  Google Scholar 

  7. El-Yaniv R., Kaniel R., Linial N. (1999) Competitive optimal on-line leasing. Algorithmica 25, 116–140

    Article  Google Scholar 

  8. El-Yaniv R., Karp R.M. (1997) Nearly optmal competitive online replacement policies. Math. Oper. Res. 22, 814–839

    Article  Google Scholar 

  9. Fiat, A., Woeginger, G.J.: On-line algorithms: the state of art. Lecture Notes in Computer Science, vol. 1442. Springer-Verlag, Berlin, Heidelberg, New York (1998)

  10. Fujiwara H., Iwama K.: Average-case competitive analyses for ski-rental problems. In: The 13th Annual International Symposium on Algorithms and Computation, pp. 476–488 (2002)

  11. Immanuel M.B. (1997) Evolution towards the maximum clique. J. Global Optim. 10, 143–164

    Article  Google Scholar 

  12. Iwama, K., Yonezawa, K.: Using generalized forecasts for on-line currency comversion. In: The 5th International Computing and Combinatorics Conference, pp. 409–421 (1999)

  13. Karlin A.R., Manaees M.S., McGeogh L., Owichi S. (1994) Competitive randomized algorithms for nonuniform problems. Algorithmica 11, 542–571

    Article  Google Scholar 

  14. Karp, R.: On-line algorithms versus off-line algorithms: how much is it worth to know the future? In: Proceedings IFIP 12th World Computer Congress, pp. 416–429 (1992)

  15. Ma W.M., Xu Y.F., Wang K.L. (2001) On-line k-truck problem and its competitive algorithms. J. Global Optim. 21, 15–25

    Article  Google Scholar 

  16. Ma W.M., Jane Y., Xu Y.F., James L., Wang K.L. (2002) On the on-line number of snacks problem. J. Global Optim. 24, 449–462

    Article  Google Scholar 

  17. Moller M.H., Upton C.W. (1976) Leasing, buying and the cost of capital services. J. Finance 31, 761–786

    Article  Google Scholar 

  18. Raghavan P. (1992) A statistical adversary for on-line algorithms. DIMACS Ser. Discrete Math. Theory Comput. Sci. 7, 79–83

    Google Scholar 

  19. Schall L.D. (1974) The lease-or-buy and asset acquisition decisions. J. Financ 29, 1203–1214

    Article  Google Scholar 

  20. Sleator D.D., Tarjan R.E. (1985) Amortized efficiency of list update and paging rules. Commun. ACM 28, 202–208

    Article  Google Scholar 

  21. Wei L.L. (1999) Bayeseian procedure in time sequential sample plan of geometric distribution. Acta Mathem. Appl. Sin. 22, 54–70

    Google Scholar 

  22. Wei L.L., Zhang W.X. (2003) A class of bayesian stopping and decision rule of geometric distribution. Math. Appl. Sin. 26, 181–185

    Google Scholar 

  23. Woeginger G.J., Zhang G.C. (1999) Optimal on-line algorithms for variable-sized bin covering. Oper. Res. Lett. 25, 47–50

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. The State Key Lab for Manufacturing Systems Engineering, School of Management, Xi’an Jiaotong University, Xi’an, 710049, China

    Yinfeng Xu

  2. School of Business Administration, South China University of Technology, Guangzhou, 510641, China

    Weijun Xu

  3. Business Administration Faculty, The Chinese University of Hong Kong, Shatin, N.T, Hong Kong

    Hongyi Li

Authors
  1. Yinfeng Xu
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Weijun Xu
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Hongyi Li
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Weijun Xu.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Xu, Y., Xu, W. & Li, H. On the on-line rent-or-buy problem in probabilistic environments. J Glob Optim 38, 1–20 (2007). https://doi.org/10.1007/s10898-006-9079-z

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10898-006-9079-z

Keywords

Search

Navigation