Processing math: 100%
We use cookies to improve your experience with our site.

Indexed in:

SCIE, EI, Scopus, INSPEC, DBLP, CSCD, etc.

Submission System
(Author / Reviewer / Editor)
Chun-Lin Xin, Wei-Min Ma, Lei Yang. Competitive Analysis of Two Special Online Device Replacement Problems[J]. Journal of Computer Science and Technology, 2008, 23(2): 203-213.
Citation: Chun-Lin Xin, Wei-Min Ma, Lei Yang. Competitive Analysis of Two Special Online Device Replacement Problems[J]. Journal of Computer Science and Technology, 2008, 23(2): 203-213.

Competitive Analysis of Two Special Online Device Replacement Problems

More Information
  • Revised Date: December 05, 2007
  • Published Date: March 14, 2008
  • When anew investment opportunity of purchasing a new deviceoccurs, the investors must decide whether or not and when to buy this device in anonline fashion. That is, the online player must make an investment decision whileneither future demand for orders nor future investment opportunities are known. Thisproblem which generalizes the basic leasing problem has been introduced by Azar {\itet al.}, and then two special cases have been studied by Damaschke. In the so-calledequal prices model a 2-competitive algorithm is devised and a 1.618 lowerbound is given. Here we make use of an averaging technique and obtain a better tightlower bound of 2, in other words, this lower bound cannot be improved.Furthermore, another special case which only considerstwo-stage device replacement is studied in this paper.Accounting for the interest rate is an essential featureof any reasonable financial model. Therefore, we explorethe two-stage model with and without the interest raterespectively. In addition, we introduce the risk-rewardmodel to analyze this problem and improve the competitive ratio performance.
  • [1]
    Azar Y, Bartal Y, Feuerstein E -\it et al.} On capital investment. -\it Algorithmica}, 1999, 25: 22--36.
    [2]
    El-Yaniv R, Karp R M. Nearly optimal competitive online replacement policies. -\it Mathematics of Operations Research}, 1997, 22(4): 814--839.
    [3]
    Damaschke P. Nearly optimal strategies for special cases of on-line capital investment. -\it Theoretical Computer Science}, 2003, 302: 35--44.
    [4]
    Johnson R W, Lewellen W G. Analysis of the lease-or-buy decision. -\it Journal of Finance}, 1972, 27: 815--824.
    [5]
    Miller M H, Upton C W. Leasing, buying and the cost of capital services. -\it Journal of Finance}, 1976, 31: 761--786.
    [6]
    S al-Binali. A risk-reward framework for the competitive analysis of finanicial games. -\it Algorithmica}, 1999, 25: 99--115.
    [7]
    El-Yaniv R, Kaniel R, Linial N. Competitive optimal on-line leasing. -\it Algorithmica}, 1999, 25: 116--140.
    [8]
    Bower R S. Issues in lease financing. -\it Financial Management}, 1973, 2: 25--33.
    [9]
    Fleischer R. On the Bahncard problem. -\it Theoretical Computer Science}, 2001, 268(1): 161--174.
    [10]
    Karlin A R, Kenyon C, Randall D. Dynamic TCP acknowledgement and other stories about e/(e1). -\it Algorithmica}, 2003, 36(3): 209--224.
    [11]
    Xu Y F, Xu W J. Competitive algorithms for online leasing problem in probabilistic environments. In -\it Proc. ISNN'04}, Dalian, China, -\it Lecture Notes in Computer Science}, 3174, Springer-Verlag, 2004, pp.725--730.
    [12]
    Ding L L, Xin C L, Chen J. A risk-reward competitive analysis of the Bahncard problem. In -\it Proc. AAIM'05}, Xi'an, China, -\it Lecture Notes in Computer Science}, 3521, Springer-Verlag, 2005, pp.37--45.
    [13]
    Xu Y F, Xin C L, Yi F L. New results on online replacement problem. In -\it Proc. WINE'05}, Hong Kong, -\it Lecture Notes in Computer Science}, -3828}, Springer-Verlag, 2005, pp.554--563.
    [14]
    Xu Y F, Xu W J, Li H Y. On the on-line rent-or-buy problem in probabilistic environments. -\it Journal of Global Optimization}, 2007, 38(1): 1--20.
    [15]
    Sleator D D, Tarjan R E. Amortized efficiency of list update and paging rules. -\it Communications of the ACM}, 1985, 28: 202--208.
    [16]
    Karlin A, Manasse M, Rudolph L -\it et al}. Competitive snoopy caching. -\it Algorithmica}, 1988, 3: 79--119.
    [17]
    Sui Y F. Two online algorithms for the ambulance systems. -\it Journal of Computer Science and Technology}, 2001, 16(2): 176--181.
    [18]
    Jiang Y W, He Y. Semi-online algorithms for scheduling with machine cost. -\it Journal of Computer Science and Technology}, 2006, 21(6): 984--988.
    [19]
    Borodin A, El-Yaniv R. Online Computation and Competitive Analysis. Cambridge University Press, 1998.
    [20]
    Fiat A, Woeginger G J. Online algorithms: The state of the art. -\it Workshop on the Competitive Analysis of On-line Algorithms}, Lecture Notes in Computer Science, 1442, Germany: Springer-Verlag, 1998, pp.196--231.
  • Related Articles

    [1]Mansoor Davoodi, Esmaeil Delfaraz, Sajjad Ghobadi, Mahtab Masoori. Algorithms for Handoff Minimization in Wireless Networks[J]. Journal of Computer Science and Technology, 2019, 34(4): 887-900. DOI: 10.1007/s11390-019-1948-2
    [2]Jiang Rong, Tao Qin, Bo An. Competitive Cloud Pricing for Long-Term Revenue Maximization[J]. Journal of Computer Science and Technology, 2019, 34(3): 645-656. DOI: 10.1007/s11390-019-1933-9
    [3]Yi-Wei Jiang, Yong He. Semi-Online Algorithms for Scheduling with Machine Cost[J]. Journal of Computer Science and Technology, 2006, 21(6): 984-988.
    [4]Yong He, Yi-Wei Jiang. Preemptive Semi-Online Scheduling with Tightly-Grouped Processing Times[J]. Journal of Computer Science and Technology, 2004, 19(6).
    [5]ZHOU BoSheng, WU JieYi, FEI Xiang, ZHAO Jian. PCBA: A Priority-Based Competitive Broadcasting Algorithm in Mobile AdHoc Networks[J]. Journal of Computer Science and Technology, 2003, 18(5).
    [6]HE Yong, CAI Shengyi. Semi-Online Scheduling with Machine Cost[J]. Journal of Computer Science and Technology, 2002, 17(6).
    [7]SUI Yuefei. Two Online Algorithms for the Ambulance Systems[J]. Journal of Computer Science and Technology, 2001, 16(2).
    [8]Shuai Dianxun. Concurrent Competitive Wave Approach to Hyper-Distributed Hyper-Parallel AI Processing[J]. Journal of Computer Science and Technology, 1997, 12(6): 543-554.
    [9]Shuai Dianxun. High-Order Two-Dimension Cluster Competitive Activation Mechanisms Used for Performing Symbolic Logic Algorithms of Problem Solving[J]. Journal of Computer Science and Technology, 1995, 10(2): 124-133.
    [10]Li Tao. Competition Based Neural Networks for Assignment Problems[J]. Journal of Computer Science and Technology, 1991, 6(4): 305-315.

Catalog

    Article views (40) PDF downloads (5762) Cited by()
    Related

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return