戴陽, 今井 浩, 岩野 和生, 加藤 直樹
情報処理学会研究報告アルゴリズム(AL) 1992(78) 41-48 1992年9月25日
当論文は、ある問題に対して、部分的動的アルゴリズム(rtially dynamic algorit)が与えられた時、その問題に対する準オンライン動的アルゴリズム(lly dynamic semi?Online algorit)を求める手法を提案している。ここで、準オンラインの問題とは、オンライン問題の特殊な版であり、各更新リクエストσ時に、その後のk個の更新リクエストによって削除される要素を含むO()のサイズの集合SS_σと全部のリクエストの数lが与えられているものである。もし、k=lであれば、問題は通常のオフライン問題になり、k=1ならば、全リクエストサイズが与えられた時のオンライン問題となる。最初に、O(√<#d+1>・)時間のサブセットサム問題の準オンラインアルゴリズムを与える。ここで、Kは目的の値であり、1個のリクエストのうち、#d個の削除リクエストがあるとする。また、()連結問題に対するO(√<l(+)>√<#d>√<α(,)>+l,α(,))時間のアルゴリズム(は点の数である) ()整数ナップサック問題に対するO(√<#d・K>√<α(^<1.5>,)>+l・α(^<1.5>,))時間のアルゴリズム(は目標の値である) ()0?1ナップサック問題に対するO(^<9/4>c(#d+)^<1/4>)時間のアルゴリズム(は最適値である)を与える。また、サブセットサム問題の準オンラインアルゴリズムの応用として、最大各差最小の等分割問題がO(+n^<2.5>)時間で解けることを示す。これらの時間限界は、著者らの知る限り、新しく自明ではない。This paper proposes a new approach to obtain a semi-online dynamic algorithm, given a partially dynamic algorithm. A semi-online problem is a special case of online problems, in which for each update request σ we are given a superset SS_σ of size O(k) which contains all items to be deleted in the succeeding k update requests as well as the total number of requests as well as the total number of requests. Thus, a semi-online problem has properties both of online and office problems. Notice that an offline problem is also a semi-online problem. We first develop an O(√<#d+1>・lK) time algorithm for the semi-online dynamic Subset Sum problem where K is a target value and a series of l requests, including #d deletions, is made to the initially empty set. We also devise the following semi-online dynamic algorithms: (a) an O(√<l'l+n)>√<3D>√<α(l, n)>+l・α(l, n)) time algorithm for the connectivity problem where l (resp. #d) is the number of all (resp, delete) requests and n is the number of vertices, (b) an O(√<#d・K>l√<α(lK^<1.5>, K>+l・α(lK^<1.5>, K)) time algorithm for the Integer Knapsack problem where K is the target value, and (c) an O(l^<9/4> c(#d+1)^<1/4>) time algorithm for the optimization 0-1 Knapsack problem where c is the optimal value. As an application of the semi-online dynamic Subset Sum problem, we devise an O(m+n^<2.>5) time algorithm for the minimum range balanced cut problem. To the authors' knowledge, these bounds are new and nontrivial.