サイクル上でのグラフ探索問題に対する最適なオンラインアルゴリズム

Abstract

オンライングラフ探索問題における目的は, 探索者が未知のグラフの全ての頂点を訪問することによりグラフ構造を調査し, 最後に出発点に戻ることである.ある辺の存在ならびにその長さは, 探索者がその端点を訪れるまで未知である.目的達成に要した総移動距離を探索者のコストとして定める.探索対象を平面グラフとする場合, 16競合のアルゴリズムが知られている.朝廣らは, 探索対象をサイクルグラフとする場合において, 1.5競合のアルゴリズムを与えるとともに, (1.25-ε)競合のアルゴリズムは存在しないことを示した(ここでeは任意の正定数である).本稿では, サイクルグラフに対する 最適なオンラインアルゴリズムを与える.すなわち, 1+√<3>/2(≃1.366)競合のアルゴリズムを与えるとともに, (1+√<3>/2-ε)競合のアルゴリズムは存在しないことを証明する(上記と同様, εは任意の正定数である)

The purpose of the online graph exploration problem is to visit all the nodes of a given graph and come back to the starting node with the minimum total traverse cost. However, unlike the classical traveling salesperson problem, information of the graph is given online. When an online algorithm (called a searcher) visits a node v, then it learns information on nodes and edges adjacent to v. It is known that there is a 16-competitive online algorithm for planer graphs. Recently, Asahiro et al. considered this problem on cycles and proved that there is a 1.5-competitive online algorithm, while no online algorithm can be (1.25-ε)-competitive for any positive constant e. In this paper, we give an optimal online algorithm for this problem; namely, we give a 1+√<3>/2(≃1.366)-competitive algorithm, and prove that there is no (1+√<3>/2-ε)-competitive algorithm for any positive constant ε.