02/02/2021

Competitive Analysis for Two-Level Ski-Rental Problem

Binghan Wu, Wei Bao, Dong Yuan

Keywords:

Abstract Paper Similar Papers

Abstract: In this paper, we study a two-level ski-rental problem. There are multiple commodities, each one can be “rented” (paying for on-demand usage) or “purchased” (paying for life-time usage). There is also a combo purchase available so that all commodities can be purchased as a combo. Since the usages of the commodities in future are not known in advance, to minimize the overall cost, we design an online algorithm to decide if we rent a commodity, purchase a commodity, or make a combo purchase. We first propose a deterministic online algorithm. It can achieve 3 competitive ratio, which is optimal and tight. Next, we further propose a randomized online algorithm, leading to a e^σ/(e^σ-1) competitive ratio, where σ is the ratio between the price of a single commodity and the price of combo purchase. Finally, we apply simulation to verify the theoretical competitive ratios and evaluate the actual performance against benchmarks.

The video of this talk cannot be embedded. You can watch it here:
https://slideslive.com/38948346
(Link will open in new window)
 0
 0
 0
 0
  Share    
This is an embedded video. Talk and the respective paper are published at AAAI 2021 virtual conference. If you are one of the authors of the paper and want to manage your upload, see the question "My papertalk has been externally embedded..." in the FAQ section.

Comments

Post Comment
no comments yet
code of conduct: tbd Characters remaining: 140

Similar Papers

 0
 0
 0
 0
 19:34 
 0
 0
 0
 0
 13:32 
 0
 0
 0
 0
 3:21 
 0
 0
 0
 0
 2:57 
 0
 0
 0
 0
 15:04 
 0
 0
 0
 0
 18:53 
 0
 0
 0
 0
 14:18 
 0
 0
 0
 0
 18:18 
 0
 0
 0
 0
 13:30 
 0
 0
 0
 0
 10:34 
 0
 0
 0
 0
 2:43 
 0
 0
 0
 0
 13:05 
 0
 0
 0
 0
 10:44 
 0
 0
 0
 0
 15:48 
 0
 0
 0
 0
 4:52 
 0
 0
 0
 0
 16:23 
 0
 0
 0
 0
 15:55 
 0
 0
 0
 0
 3:22 
 0
 0
 0
 0
 14:37 
 0
 0
 0
 0
 3:10 
 0
 0
 0
 0
 4:53 
 0
 0
 0
 0
 2:52 
 0
 0
 0
 0
 13:24 
 0
 0
 0
 0
 15:56 
 0
 0
 0
 0
 20:54 
 0
 0
 0
 0
 13:26 
 0
 0
 0
 0
 20:14 
 0
 0
 0
 0
 20:41 
 0
 0
 0
 0
 19:52 
 0
 0
 0
 0
 3:21 
 0
 0
 0
 0
 18:21 
 0
 0
 0
 0
 2:43 
 0
 0
 0
 0
 3:02 
 0
 0
 0
 0
 15:26 
 0
 0
 0
 0
 13:35 
 0
 0
 0
 0
 14:40 
 0
 0
 0
 0
 18:21 
 0
 0
 0
 0
 2:57 
 0
 0
 0
 0
 3:10 
 0
 0
 0
 0
 12:03