On the best possible competitive ratio for the multislope ski-rental problem
On the best possible competitive ratio for the multislope ski-rental problem
复制标题
DOI：
10.1007/s10878-014-9762-9
复制
发表时间：
2016-02
影响因子：
1
通讯作者：
H. Fujiwara;Takuma Kitano;Toshihiro Fujito
中科院分区：
文献类型：
--
作者：
H. Fujiwara;Takuma Kitano;Toshihiro Fujito
多坡道滑雪板租赁问题是经典滑雪板租赁问题的扩展，在经典的滑雪板租赁问题中，除了供应商和购买选项之外，玩家还有几种选择。在这个问题中，作为选项设置的实例的硬度对玩家的表现有很大影响。对于给定的实例，有一种算法可以计算出可能的最佳策略。但是，输出是以数值形式给出的，因此实例与其最佳可能性能之间的关系性质尚不清楚。在本文中，我们证明了即使是最简单的情况，也不能达到比竞争比小的竞争比。更准确地说，最佳性能的严格下限是以闭合形式获得的，该闭合形式由选项的数量来参数化。此外，我们还建立了3-期权和4-期权问题的竞争比的一个匹配的上下界。
The multislope ski-rental problem is an extension of the classical ski-rental problem, where the player has severalleaseoptions besides the purerentandbuyoptions. In this problem the hardness of aninstance, which is the setting of options, significantly affects the player’s performance. There is an algorithm that for a given instance, computes the best possible strategy. However, the output is given as numerical values and therefore the relational nature between an instance and the best possible performance for it has not been known. In this paper we prove that even for the easiest instance, a competitive ratio smaller thancannot be achieved. More precisely, a tight lower bound on the best possible performance is obtained in a closed form parametrized by the number of options. Furthermore, we establish a matching upper and lower bound on the competitive ratio each for the 3-option and 4-option problems.