Competitive analysis for discrete multiple online rental problems

• 来源期刊: 管理科学学报（英文版）
• 关键词: Discrete multiple online rental problem Risk control strategy Online algorithms Competitive ratio
• 年，卷（期）: 2018,（3）
• 页码范围: 125-140
• 页数: 16页
• 语种: 中文
• DOI: 10.3724/SP.J.1383.303007

摘要

Many 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 of 1/ms where m is the total units of certain assets or equipment and s is the price to buy one unit in each period.