New Lower Bound and Algorithms for Online Geometric Hitting Set Problem

The hitting set problem is one of the fundamental problems in combinatorial optimization and is well-studied in offline setup. We consider the online hitting set problem, where only the set of points is known in advance, and objects are introduced one by one. Our objective is to maintain a minimum-sized hitting set by making irrevocable decisions. Here, we present the study of two variants of the online hitting set problem depending on the point set. In the first variant, we consider the point set to be the entire mathbbZd, while in the second variant, we consider the point set to be a finite subset of ℝ2. If you use points in mathbbZd to hit homothetic hypercubes in ℝd with side lengths in [1,M], we show that the competitive ratio of any algorithm is Omega(dlog M), whether it is deterministic or random. This improves the recently known deterministic lower bound of Omega(log M) by a factor of d. Then, we present an almost tight randomized algorithm with a competitive ratio O(d2log M) that significantly improves the best-known competitive ratio of 25dlog M. Next, we propose a simple deterministic lfloorfrac2α+2rfloord(lfloorlog2Mrfloor+1) competitive algorithm to hit similarly sized α-fat objects in ℝd having diameters in the range [1, M] using points in mathbbZd. This improves the current best-known upper bound by a factor of at least 5d. Finally, we consider the hitting set problem when the point set consists of n points in ℝ2, and the objects are homothetic regular k-gons having diameter in the range [1, M]. We present an O(log nlog M) competitive randomized algorithm for that. Whereas no result was known even for squares. In particular, our results answer some of the open questions raised by Khan et al. (SoCG'23) and Alefkhani et al. (WAOA'23).