
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

The Axisbound CNN Problem
Kouki YONEZAWA Kazuo IWAMA
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E87A
No.5
pp.12351242 Publication Date: 2004/05/01
Online ISSN:
DOI:
Print ISSN: 09168508 Type of Manuscript: PAPER Category: Algorithms and Data Structures Keyword: online algorithms, CNN problem,
Full Text: PDF(368.8KB)>>
Summary:
In the CNN problem, a "scene" appears on the twodimensional plane, at different positions sequentially, and a "camera crew" has to shoot the scene whenever it appears. If a scene appears at some position, the camera crew does not have to move to the position exactly, but has only to move to a point that lies in the same horizontal or vertical line with the scene. Namely it is enough to move either to the same row or to the same column. The goal is to minimize the total moving distance of the camera crew. This problem has been quite popular in the last decade but it is still open whether or not there is a competitive algorithm, i.e., an algorithm with competitive ratio bounded by a constant. In this paper we study this problem under a natural restriction that the server can move only along the Xaxis and the Yaxis. It is shown that there exists a competitive algorithm for this restricted version, namely there is an online algorithm for this "axisbound CNN" with competitive ratio 9.0.

