Finite-State Online Algorithms and Their Automated Competitive Analysis
Finite-State Online Algorithms and Their Automated Competitive Analysis
复制标题
DOI：
10.1007/11940128_9
复制
发表时间：
2006-12
期刊：
影响因子：
--
通讯作者：
T. Horiyama;K. Iwama;J. Kawahara
中科院分区：
文献类型：
--
作者：
T. Horiyama;K. Iwama;J. Kawahara
在本文中，我们研究了可撤销的在线背包问题（ROKP），它是在线背包问题[8]的扩展。本文证明了ROKP竞争比的最优上界为1/t，其中4x 3 + 5x 2-x- 4 = 0为真实的根（t = 0.76850，1/t = 1.3012）.为了证明这一结果，我们充分利用计算机程序如下：对于以常规方式设计的基本算法，我们首先构造一个约有300个状态的等价有限状态图。然后，对于每个状态，我们生成一个有限的不等式集，使得在该状态下的竞争比至多为1/tif的不等式集没有真实的解。后者可以通过Mathematica进行检查。生成的不等式总数约为600个，我们使用Athlon XP 2600+的计算时间为30分钟。
In this paper we study the Revocable Online Knapsack Problem (ROKP) which is an extension of the Online Knapsack Problem [8]. We prove an optimal upper bound of 1/tfor the competitive ratio of ROKP, wheretis a real root of 4x3+ 5x2–x– 4 = 0 (t≈0.76850 and 1/t≈1.3012). To prove this result, we made a full use of computer programs as follows: For the base algorithm that is designed in a conventional manner, we first construct an equivalent finite state diagram with about 300 states. Then for each state, we generate a finite set of inequalities such that the competitive ratio at that state is at most 1/tif the set of inequalities do not have a real solution. The latter can be checked by Mathematica. The number of inequalities generated was approximately 600 in total, and our computation time was 30 minutes using Athlon XP 2600+.