1. School of Mathematical Science, Huaiyin Normal University, Huai'an 223300, China; 2. School of Business Administration, South China University of Technology, Guangzhou 510641, China
Abstract：The two-slope online leasing problem is a natural generalization of the classic online leasing problem. Due to the fact that the two-slope online leasing problem of continuous-time has already been studied, we focus on the two-slope online leasing problem of discrete time in this study. Our discussion has taken the deterministic strategy and the randomized strategy into consideration. We demonstrated an optimal deterministic strategy, which could achieve competitive factor of 2-[1+(s-1)a]/s. As for the randomized strategy, we proposed the strategy of risk balanced its absolute optimality through competitive analysis. Finally, analysis and discussions are carried out for the two types of strategies, mainly based on their competitive performances. It is found that, the two-slope analysis could improve the competitive ratio of the classic online leasing problems. In addition, by taking the discreteness into consideration rather than the continuity, the effectiveness of solving online leasing problem could be much improved.
胡茂林, 徐维军. 离散型两斜率在线租赁问题[J]. 系统工程理论与实践, 2019, 39(7): 1680-1689.
HU Maolin, XU Weijun. Discrete online leasing problem with two slopes. Systems Engineering - Theory & Practice, 2019, 39(7): 1680-1689.
[1] Karlin A R, Manasse M S, Rudolph L, et al. Competitive snoopy caching[J]. Algorithmica, 1988, 3(1):77-119. [2] Karlin A R, Manasse M S, McGeoch L A, et al. Competitive randomized algorithms for nonuniform problems[J]. Algorithmica, 1994, 11(6):542-571. [3] Karp R. On-line algorithms versus off-line algorithms:How much is it worth to know the future?[C]//Proc IFIP 12th World Computer Congress, The Netherlands:North-Holland Publishing Co., 1992, 1:416-429. [4] El-Yaniv R, Kaniel R, Linial N. Competitive optimal online leasing[J]. Algorithmica, 1999, 25(1):116-140. [5] Azar Y, Bartal Y, Feuerstein E, et al. On capital investment[J]. Algorithmica, 1999, 25(1):22-36. [6] Bejerano Y, Cidon I, Naor J. Dynamic session management for static and mobile users:A competitive on-line algorithmic approach[C]//Proceedings of the 4th International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications, 2000:65-74. [7] Damaschke P. Nearly optimal strategies for special cases of on-line capital investment[J]. Theoretical Computer Science, 2003, 302(1-3):35-44. [8] Abshoff S, Kling P, Markarian C, et al. Towards the price of leasing online[J]. Journal of Combinatorial Optimization, 2015, 24:1-20. [9] Li S, Mäcker A, Markarian C, et al. Towards flexible demands in online leasing problems[J]. Computing and Combinatorics, 2015, 9198(5):277-288. [10] Dai W, Dong Y, Zhang X. Competitive analysis of the online financial lease problem[J]. European Journal of Operational Research, 2016, 250:865-873. [11] Lotker Z, Patt-Shamir B, Rawitz D. Ski rental with two general options[J]. Information Processing Letters, 2008, 108(1):339-422. [12] Leve A, Patt-Shamir B. Non-additive two-option ski rental[J]. Theoretical Computer Science, 2015, 584:42-52. [13] 陈晓丽, 徐维军. 复利下二重在线租赁竞争策略及风险补偿模型[J]. 系统工程理论与实践, 2016, 36(9):2284-2292.Chen X L, Xu W J. Competitive strategy and risk-reward model with compound rate for online fashion A-B leasing problem[J]. Systems Engineering-Theory & Practice, 2016, 36(9):2284-2292. [14] Lotker Z, Patt-Shamir B, Rawitz D. Rent, lease or buy:Randomized algorithms for multislope ski rental[J]. SIAM Journal on Discrete Mathematics, 2012, 26(2):718-736. [15] Fujiwara H, Kitano T, Fujito T. On the best possible competitive ratio for multislope ski rental[C]//Proceedings of the 22th International Conference on Algorithms and Computation, 2011:544-553. [16] Hu M L, Xu W J. A better bound of randomized algorithms for the multislope ski-rental problem[J]. RAIRO-Theoretical Informatics and Applications, 2017, 51(16):91-98.
2019, Vol. 39 
