The hitting set problem is a fundamental and well-studied combinatorial optimization problem in the offline setup. We study the online hitting set problem, where we know only the set of points beforehand, and objects are introduced individually. The objective is to maintain a minimum-sized hitting set by making irrevocable decisions. To hit homothetic axis-aligned hypercubes in \(\mathbb {R}^d\) having widths in the range [1, M] using points in \(\mathbb {Z}^d\) , we show that the competitive ratio of any algorithm, whether deterministic or randomized, is \(\varOmega (d\log M)\) . Then, we propose a deterministic \({\lfloor 4\alpha +1\rfloor ^d}\) \(\lfloor \log _{2}2M\rfloor \) competitive algorithm to hit \(\alpha \) -fat objects in \(\mathbb {R}^d\) having widths in the range [1, M] using points in \(\mathbb {Z}^d\) . When the set of points is restricted to \((0, N)^d\cap \mathbb {Z}^d\) and the \(\alpha \) -fat objects are in \((0, N)^d\) , we obtain \(\varOmega (d\log N)\) and \(O((4\alpha +1)^{d}\log N)\) , respectively, as the lower and upper bounds of the competitive ratio. This answers an open question raised by Alefkhani, Khodaveis, and Mari (WAOA 2023) by improving the best-known lower and upper bounds of \(\varOmega (\log N)\) and \(O((4\alpha +1)^{2d}\log N)\) , respectively, obtained by them for the problem. The techniques used are simple yet nontrivial, highlighting our paper’s strength.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

New Lower Bound and Algorithm for Online Geometric Hitting Set Problem

  • Minati De,
  • Ratnadip Mandal,
  • Satyam Singh

摘要

The hitting set problem is a fundamental and well-studied combinatorial optimization problem in the offline setup. We study the online hitting set problem, where we know only the set of points beforehand, and objects are introduced individually. The objective is to maintain a minimum-sized hitting set by making irrevocable decisions. To hit homothetic axis-aligned hypercubes in \(\mathbb {R}^d\) having widths in the range [1, M] using points in \(\mathbb {Z}^d\) , we show that the competitive ratio of any algorithm, whether deterministic or randomized, is \(\varOmega (d\log M)\) . Then, we propose a deterministic \({\lfloor 4\alpha +1\rfloor ^d}\) \(\lfloor \log _{2}2M\rfloor \) competitive algorithm to hit \(\alpha \) -fat objects in \(\mathbb {R}^d\) having widths in the range [1, M] using points in \(\mathbb {Z}^d\) . When the set of points is restricted to \((0, N)^d\cap \mathbb {Z}^d\) and the \(\alpha \) -fat objects are in \((0, N)^d\) , we obtain \(\varOmega (d\log N)\) and \(O((4\alpha +1)^{d}\log N)\) , respectively, as the lower and upper bounds of the competitive ratio. This answers an open question raised by Alefkhani, Khodaveis, and Mari (WAOA 2023) by improving the best-known lower and upper bounds of \(\varOmega (\log N)\) and \(O((4\alpha +1)^{2d}\log N)\) , respectively, obtained by them for the problem. The techniques used are simple yet nontrivial, highlighting our paper’s strength.