Competitive Analysis for the Online Rental Problem with Multiple Options

The online algorithm and competitive analysis provides a powerful tool to deal with uncertain decision making problems.Applying this tool,many researchers study rental problems in details.These studies are on the basis of Karp 's ski-rental model,and the player only has two choices: lease or buy.And the algorithm needs to decide when to switch from renting to buying.However,in realistic rental markets(e.g.vehicle rental market,house rental market),the player often has multiple rental options.In this paper,we construct a rental model with multiple options,and present an online deterministic algorithm for this problem with a matching lower bound.