*Title:* Hitting Sets Online
*Speaker:* Guy Even, Tel-Aviv University

*Abstract: *We consider the hitting set problem in an online setting. In 
this setting a hypergraph over a ground set X is unknown in advance. A 
sequence of hyperedges S_i (i.e., S_i is a subset of X) arrive one by 
one in an online fashion. Upon arrival of a hyperedge S_i, the algorithm 
must select an element in S_i. The goal is to select as few elements as 
possible. We define a new hypergraph property, called the hitting set 
competitive ratio of H. This property equals the smallest competitive 
ratio of an online algorithm for hitting sets with respect to the 
hypergraph H.

We consider hypergraphs in which the union of every two intersecting 
hyperedges is also a hyperedge. We prove that the hitting set 
competitive ratio of such a hypergraph H equals the minimum number of 
colors needed to color the hypergraph in a unique-max coloring. In such 
a coloring, the maximum color in each hyperedge appears exactly once.

We apply this result as follows:

    * Given a graph G, consider the hypergraph consisting of connected
      subgraphs of G induced by subsets of vertices. For such a
      hypergraph, we obtain improved competitive ratios compared to
      [Alon, Azar, Buchbinder, Naor; 2003] if G is a planar graph or has
      bounded tree-width.

    * We consider hypergraphs realized by points in the plane and half
      planes or unit disks. For these cases we obtain a logarithmic
      competitive ratio.


Joint work with Shakhar Smorodinsky (presented in ESA-2011)