We consider the online hitting set problem for the range space $\Sigma=(\cal X,\cal R)$, where the point set $\cal X$ is known beforehand, but the set $\cal R$ of geometric objects is not known in advance. Here, geometric objects arrive one by one, the objective is to maintain a hitting set of minimum cardinality by taking irrevocable decisions. In this paper, we have considered the problem when the objects are unit balls or unit hypercubes in $\mathbb{R}^d$, and the points from $\mathbb{Z}^d$ are used for hitting them. First, we consider the problem for objects (unit balls and unit hypercubes) in lower dimensions. We obtain $4$ and $8$-competitive deterministic online algorithms for hitting unit hypercubes in $\mathbb{R}^2$ and $\mathbb{R}^3$, respectively. On the other hand, we present $4$ and $14$-competitive deterministic online algorithms for hitting unit balls in $\mathbb{R}^2$ and $\mathbb{R}^3$, respectively. Next, we consider the problem for objects (unit balls and unit hypercubes) in the higher dimension. For hitting unit hypercubes in $\mathbb{R}^d$, we present a $O(d^2)$-competitive randomized online algorithm for $d\geq 3$ and prove the competitive ratio of any deterministic algorithm for the problem is at least $d+1$ for any $d\in\mathbb{N}$. Then, for hitting unit balls in $\mathbb{R}^d$, we propose a $O(d^4)$-competitive deterministic algorithm, and for $d<4$, we establish that the competitive ratio of any deterministic algorithm is at least $d+1$.
翻译:在$\mathbb{Z}^d$中使用点数击中$\mathbb{R}^d$中单位球和超立方体的在线问题。
我们考虑一个范围空间$\Sigma=(\cal X,\cal R)$的在线击中集问题,其中点集$\cal X$预先知道,但几何对象的集合$\cal R$事先不知道。在这里,几何对象一个接一个地到达,目标是通过做出不可撤销的决策来维护最小的击中集。在本文中,我们考虑了物体为单位球或单位 d 维超立方体的问题,使用来自$\mathbb{Z}^d$的点数进行击中。首先,我们考虑低维物体(单位球和单位超立方体)的问题。 对于在$\mathbb{R}^2$和$\mathbb{R}^3$中的单位超立方体击中,我们得到了$4$和$8$的竞争力的确定性在线算法;对于在$\mathbb{R}^2$和$\mathbb{R}^3$中的单位球击中,我们提出了$4$和$14$的竞争力的确定性在线算法。 接下来,我们考虑更高维度的问题。针对在$\mathbb{R}^d$中的单位超立方体敲定,我们提出了一个$O(d^2)$的随机在线算法,对于任何$d\in\mathbb{N}$,证明了该问题的任何确定性算法的竞争比至少为$d+1$。然后,对于在$\mathbb{R}^d$中敲定单位球,我们提出了一个$O(d^4)$的确定性算法,对于$d<4$,我们确定任何确定性算法的竞争比至少为$d+1$。