期刊
IEEE-ACM TRANSACTIONS ON NETWORKING
卷 30, 期 6, 页码 2804-2817出版社
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/TNET.2022.3183142
关键词
Online algorithms; competitive ratio; switching cost; minimum commitment
类别
资金
- National Natural Science Foundation of China [62072096]
- International S&T Cooperation Program of Shanghai Science and Technology Commission [20220713000]
- Shuguang Program of Shanghai Education Development Foundation
- Shanghai Municipal Education Commission [20SG32]
- Young Top-Notch Talent Program in Shanghai
- Fundamental Research Funds for the Central Universities
- Graduate Student Innovation Fund of Donghua University [CUSF-DH-D-2020086]
This paper investigates an online decision problem of when to buy and cancel a discount plan to minimize overall cost. The authors propose deterministic and randomized online algorithms and optimize them for different scenarios.
In this paper, we consider an online decision problem, where a decision maker has an option to buy a discount plan for his/her regular expenses. The discount plan costs an immediate upfront charge plus a commitment charge per time slot. Upon expiration, the discount period can be extended if the decision maker continues paying the commitment charge, or be canceled if he or she decides not to pay the commitment charge anymore. We investigate online algorithms for the decision maker to decide when to buy the discount plan and when to cancel it without the knowledge of his/her future expenses, aiming at minimizing the overall cost. The problem is an extension of the classic Bahncard Problem, which is applicable for a wide range of online decision scenarios. We propose a novel deterministic online algorithm which can achieve a closed-form competitive ratio upper bounded by 4. We further propose a randomized online algorithm with a smaller competitive ratio and two variants tailored for average-case inputs and time-varying parameters, respectively. Lastly, we evaluate our algorithms against state-of-the-art online benchmark algorithms in two real-world scenarios.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据