• Articles • Previous Articles     Next Articles

Competitive Analysis of Two Special Online Device Replacement Problems

Chun-Lin Xin1, Wei-Min Ma2, and Lei Yang1   

  1. 1School of Economics and Management, Tsinghua University, Beijing 100084, China 2School of Economics and Management, Tongji University, Shanghai 200092, China
  • Revised:2007-12-06 Online:2008-03-15 Published:2008-03-10

When a new investment opportunity of purchasing a new device occurs, the investors must decide whether or not and when to buy this device in an online fashion. That is, the online player must make an investment decision while neither future demand for orders nor future investment opportunities are known. This problem which generalizes the basic leasing problem has been introduced by Azar {\it et al.}, and then two special cases have been studied by Damaschke. In the so-called equal prices model a $2$-competitive algorithm is devised and a 1.618 lower bound is given. Here we make use of an averaging technique and obtain a better tight lower bound of $2$, in other words, this lower bound cannot be improved. Furthermore, another special case which only considers two-stage device replacement is studied in this paper. Accounting for the interest rate is an essential feature of any reasonable financial model. Therefore, we explore the two-stage model with and without the interest rate respectively. In addition, we introduce the risk-reward model to analyze this problem and improve the competitive ratio performance.

Key words: agent; mobile agent; information service; client/server; Java;

[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/(e-1)$. -\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.
[1] Yan Zheng, Jian-Ye Hao, Zong-Zhang Zhang, Zhao-Peng Meng, Xiao-Tian Hao. Efficient Multiagent Policy Optimization Based on Weighted Estimators in Stochastic Cooperative Environments [J]. Journal of Computer Science and Technology, 2020, 35(2): 268-280.
[2] Mahsa Chitsaz, and Chaw Seng Woo, Member, IEEE. Software Agent with Reinforcement Learning Approach for Medical Image Segmentation [J]. , 2011, 26(2): 247-255.
[3] Xin-Dong Wu, Senior Member, IEEE, Xing-Quan Zhu, Member, ACM, IEEE, Qi-Jun Chen, and Fei-Yue Wang, Member, ACM, Fellow, IEEE. Ubiquitous Mining with Interactive Data Mining Agents [J]. , 2009, 24(6): 1018-1027.
[4] Anna Gutowska, Andrew Sloane, and Kevan A. Buckley. On Desideratum for B2C E-Commerce Reputation Systems [J]. , 2009, 24(5): 820-832.
[5] Sarbani Roy and Nandini Mukherjee, Member, IEEE. Adaptive Execution of Jobs in Computational Grid Environment [J]. , 2009, 24(5): 925-938.
[6] Zhong-Zhi Shi and Nan-Ning Zheng. Progress and Challenge of Artificial Intelligence [J]. , 2006, 21(5): 810-822 .
[7] Jie Wang, Shi-Er Ju, and Chun-Nian Liu. Agent-Oriented Probabilistic Logic Programming [J]. , 2006, 21(3): 412-417 .
[8] Menq-Wen Lin, K. Robert Lai, and Ting-Jung Yu. Fuzzy Constraint-Based Agent Negotiation [J]. , 2005, 20(3): 319-330 .
[9] Swapan Bhattacharya[1], Anirban Banerjee[2], and Shibdas Bandyopadhyay[3]. CORBA-Based Analysis of Multi Agent Behavior [J]. , 2005, 20(1): 0-0.
[10] Chang-Jun Jiang, Zhao-Hui Zhang, Guo-Sun Zeng et al.. Urban Traffic Information Service Application Grid [J]. , 2005, 20(1): 0-0.
[11] Bi-Xin Li, Xiao-Cong Fan, Jun Pang, and Jian-Jun Zhao. Model for Slicing JAVA Programs Hierarchically [J]. , 2004, 19(6): 0-0.
[12] CHEN Lin (陈 琳), WANG ChoLi (王卓立) and Francis C. M. Lau. A Grid Middleware for Distributed Java Computing with MPI Binding and Process Migration Supports [J]. , 2003, 18(4): 0-0.
[13] WANG ChangJie (王常杰), ZHANG FangGuo (张方国) and WANG YuMin (王育民). Secure Web Transaction with Anonymous Mobile Agent over Internet [J]. , 2003, 18(1): 0-0.
[14] LU Zhengding (卢正鼎), LI Chunlin (李春林) and LI Layuan (李腊元). Coordinating Mobile Agents by the XML-Based Tuple Space [J]. , 2002, 17(6): 0-0.
[15] ZHOU Chong (周冲) and SUN Yongqiang (孙永强). SPMH: A Solution to the Problem of Malicious Hosts [J]. , 2002, 17(6): 0-0.
Full text



[1] Liu Mingye; Hong Enyu;. Some Covering Problems and Their Solutions in Automatic Logic Synthesis Systems[J]. , 1986, 1(2): 83 -92 .
[2] Chen Shihua;. On the Structure of (Weak) Inverses of an (Weakly) Invertible Finite Automaton[J]. , 1986, 1(3): 92 -100 .
[3] Gao Qingshi; Zhang Xiang; Yang Shufan; Chen Shuqing;. Vector Computer 757[J]. , 1986, 1(3): 1 -14 .
[4] Chen Zhaoxiong; Gao Qingshi;. A Substitution Based Model for the Implementation of PROLOG——The Design and Implementation of LPROLOG[J]. , 1986, 1(4): 17 -26 .
[5] Huang Heyan;. A Parallel Implementation Model of HPARLOG[J]. , 1986, 1(4): 27 -38 .
[6] Min Yinghua; Han Zhide;. A Built-in Test Pattern Generator[J]. , 1986, 1(4): 62 -74 .
[7] Tang Tonggao; Zhao Zhaokeng;. Stack Method in Program Semantics[J]. , 1987, 2(1): 51 -63 .
[8] Min Yinghua;. Easy Test Generation PLAs[J]. , 1987, 2(1): 72 -80 .
[9] Zhang Bo; Zhang Ling;. Statistical Heuristic Search[J]. , 1987, 2(1): 1 -11 .
[10] Zhu Hong;. Some Mathematical Properties of the Functional Programming Language FP[J]. , 1987, 2(3): 202 -216 .

ISSN 1000-9000(Print)

CN 11-2296/TP

Editorial Board
Author Guidelines
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
E-mail: jcst@ict.ac.cn
  Copyright ©2015 JCST, All Rights Reserved