文章基本信息

标题：Competitive Analysis for Discrete Multiple Online Rental Problems
本地全文：下载
作者：Maolin Hu ; Weijun Xu ; Hongyi Li 等
期刊名称：Journal of Management Science and Engineering
印刷版ISSN：2096-2320
出版年度：2018
卷号：3
期号：3
页码：125-140
DOI：10.3724/SP.J.1383.303007
语种：English
出版社：Elsevier
摘要：AbstractMany actual rental activities present online rental problems with multiple units of assets or equipment whose use can be continuous, separable, or discrete. Using online algorithms and competitive analysis, continuous multiple online rental problems have obtained the optimal risk control strategy and the optimal competitive ratio. For multiple online rental problems with discrete assets, first, we present an approximation algorithm for a risk control strategy and the upper bound of the optimal competitive ratio. Moreover, in practical applications, the approximation algorithm of the discrete online problem provides the approximate rental quantities in each period and the solution principle for the approximate competitive ratio. Second, we present the approximate optimal rental quantities and the correction algorithm to obtain a better competitive ratio based on the approximation algorithm. Finally, we compare the approximation algorithm with the correction algorithm by real data. Our findings show that when the approximate solution is used to replace the corrected solution, the resulting approximation error is usually less than the magnitude of1mswheremis the total units of certain assets or equipment andsis the price to buy one unit in each period.
关键词：Discrete multiple online rental problem;Risk control strategy;Online algorithms;Competitive ratio