Online hitting sets in a geometric setting via vertex ranking Academic Article uri icon

abstract

  • Abstract We consider the problem of hitting sets online. The hypergraph (ie, range-space consisting of points and ranges) is known in advance. However, the ranges to be stabbed are input one-by-one in an online fashion. The online algorithm must stab each range upon arrival. An online algorithm may add points to the hitting set but may not remove already chosen points. The goal is to use the smallest number of points. The best known competitive ratio for online hitting sets by Alon et al.[1] is O (log n· log m) for general hypergraphs, where n and m denote the number of points and the number of ranges, respectively. We consider three special classes of hypergraphs. The first setting consists of subsets of nodes of a given graph that induce connected subgraphs. We show how vertex ranking can be employed to design a simple online algorithm, the competitive ratio of which equals the number of …

publication date

  • January 1, 2011