The Axis-bound CNN Problem

Kouki YONEZAWA; Kazuo IWAMA

The Axis-bound CNN Problem

Kouki YONEZAWA, Kazuo IWAMA

Full Text Views

0

Share
Cite this

Summary :

In the CNN problem, a "scene" appears on the two-dimensional 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 X-axis and the Y-axis. It is shown that there exists a competitive algorithm for this restricted version, namely there is an online algorithm for this "axis-bound CNN" with competitive ratio 9.0.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E87-A No.5 pp.1235-1242

Publication Date: 2004/05/01

Publicized

Online ISSN

DOI

Type of Manuscript: PAPER

Category: Algorithms and Data Structures

Cite this

Copy

Kouki YONEZAWA, Kazuo IWAMA, "The Axis-bound CNN Problem" in IEICE TRANSACTIONS on Fundamentals, vol. E87-A, no. 5, pp. 1235-1242, May 2004, doi: .
Abstract: In the CNN problem, a "scene" appears on the two-dimensional 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 X-axis and the Y-axis. It is shown that there exists a competitive algorithm for this restricted version, namely there is an online algorithm for this "axis-bound CNN" with competitive ratio 9.0.
URL: https://globals.ieice.org/en_transactions/fundamentals/10.1587/e87-a_5_1235/_p

Copy

@ARTICLE{e87-a_5_1235,
author={Kouki YONEZAWA, Kazuo IWAMA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={The Axis-bound CNN Problem},
year={2004},
volume={E87-A},
number={5},
pages={1235-1242},
abstract={In the CNN problem, a "scene" appears on the two-dimensional 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 X-axis and the Y-axis. It is shown that there exists a competitive algorithm for this restricted version, namely there is an online algorithm for this "axis-bound CNN" with competitive ratio 9.0.},
keywords={},
doi={},
ISSN={},
month={May},}

Copy

TY - JOUR
TI - The Axis-bound CNN Problem
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1235
EP - 1242
AU - Kouki YONEZAWA
AU - Kazuo IWAMA
PY - 2004
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E87-A
IS - 5
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - May 2004
AB - In the CNN problem, a "scene" appears on the two-dimensional 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 X-axis and the Y-axis. It is shown that there exists a competitive algorithm for this restricted version, namely there is an online algorithm for this "axis-bound CNN" with competitive ratio 9.0.
ER -