Improved Online Hitting Set Algorithms for Structured and Geometric Set Systems

Our main results answer this question positively. Recall that the VC dimension of a set system is the largest set of elements that can be shattered. The shallow cell complexity ${\phi }_{ℱ}(\cdot ,\cdot )$ is a finer-grained notion, bounding the number of sets of size $k$ in any restriction of the set system to $\mathrm{\ell }$ elements.

We demonstrate that online relax-and-round approaches can be successfully combined with net-finding and quasi-uniform sampling offline algorithms to resolve open problems in the area. The first step in both the unweighted and weighted cases is to use an online algorithm for fractional hitting set, losing an $O(\log n)$-factor in the competitive ratio. Starting from [18], we know that rounding a fractional solution reduces to finding an $\epsilon$-net in a set-system, where each element $e$ with fractional value $x_e$ is replaced by $\lceil n{x}_e\rceil$ clones. Since the fractional solution is feasible, each set in the original instance now contains at least $n$ clones, so finding a hitting set in the original instance reduces to finding an $\epsilon$-net (for $\epsilon =1/n$) that hits all sets of size at least $n$ in this new set system $𝒥$. We start with the elegant algorithm of [22], which first samples each element with a certain base probability; now, for any large set $T$ not hit by this sample, it selects elements of $T$ independently with probability proportional to $1/|T|$ into the sample.

Carrying out this procedure in the online setting has two main issues: firstly, the fractional solution evolves over time, and the $x_e$ values may increase as sets arrive. As a result, if an element $e$ is contained in sets $S_1$ and $S_2$, the number of clones of $e$ in the corresponding sets in the new set system $𝒥$ may be different, which affects the VC dimension and the SCC of $𝒥$. Secondly, the initial sampling step in [22] requires knowledge of all the elements in the set system; but in the online setting, new clones of an element appear when its fractional value increases. We handle the first issue by showing that the VC dimension and the SCC of the new set system $𝒥$ can be related to those of the original instance, and for the second issue, we replace the sampling step by a deferred sampling step.

The online algorithm for weighted hitting set adapts the quasi-uniform sampling algorithm of [8] to the online setting. This algorithm builds a chain of nested sets of clones, starting with the entire set $V_0$ of clones, with each subsequent set $V_{\mathrm{\ell }}$ having size $(1/2+{\delta }_{\mathrm{\ell }})$ times the size of $V_{\mathrm{\ell }-1}$. Here ${\delta }_{\mathrm{\ell }}$ is a small bias term, which ensures that most sets $S$ of the hitting set instance have at least half their elements survive to the next level. Sets whose size falls below $n/2^{\mathrm{\ell }}$ are said to be “dangerous” and must select a “backup” element to hit them. The choice of this backup element is done to ensure that no element is picked too often. Apart from the challenge of the new clones arriving online, finding the backups seems like an inherently offline problem, since it seems to require knowing the entire set system. However, we view the problem of finding backup elements as a load-balancing problem, and show how to choose backups that increases the probability by a logarithmic factor. Existing presentations of the algorithm also build the layers iteratively, discarding sets that are covered by each layer to get the set system for the next layer – we observe that these optimizations are inessential, and removing them allows a clean online implementation. (See Algorithm 4 in Section 5.)

For a set system $(U,ℱ)$ and a subset $U^{\prime }\subset U$, denote the induced collection of sets as ${ℱ}_{U^{\prime }}:=\{S\cap U^{\prime }\mid S\in ℱ\}$.

Crucially, the number of distinct sets in ${ℱ}_{U^{\prime }}$ is bounded by $\mathrm{\ell }\cdot \phi (\mathrm{\ell },k)$ rather than the worst-case $\left(\genfrac{}{}{0pt}{}{\mathrm{\ell }}{k}\right)$. If the VC dimension of the set system $ℐ$ is $d$, the shattering lemma [25, Ch. 15] implies that $\mathrm{\ell }\cdot \phi (\mathrm{\ell },k)\le \left(\genfrac{}{}{0pt}{}{\mathrm{\ell }}{d}\right)\approx {(\text{e}\mathrm{\ell }/d)}^d$.

We focus on functions $\phi$ which are well-behaved, in the sense of [23].

Well-behavedness is easy to verify for the common case of $\phi (\mathrm{\ell },k)=k^c$ for some constant $c\ge 0$. Henceforth, our focus will be on such functions.

We consider the following offline algorithm for finding $\epsilon$-nets (see Algorithm 2) [23]. The algorithm maintains a subset $H$ of $V^{\prime }$, which is initialized to the empty set. In the base sampling step (line 2), each element in $V^{\prime }$ is added to $H$ with probability $\alpha /B$. In the alteration step (line 5), we consider each set $T_t$. While a set $T_t$ is not yet hit by some element in $H$, we add each element in $T_t$ to the set $H$ independently with probability $\beta /|T_t|$.

Let $\epsilon$ denote $B/N^{\prime }$. Since each set in $𝒢$ has size at least $B$, any $\epsilon$-net in the set system $(V^{\prime },𝒢)$ must hit all the sets in $𝒢$. The following guarantee now follows from [23, Theorem 7.6]:

We show how to implement Algorithm 2 online. There are two technical difficulties:

1. (i)

   The parameter $\alpha$ used in Algorithm 2 depends on $N^{\prime }$ (see Theorem 7). But in the online setting, elements contained in a set are revealed over time, and hence $N^{\prime }$ changes over time. We address this using a standard doubling trick: we divide the execution into phases. In a single phase, the value of $N^{\prime }$ lies in the range $[2^a,2^{a+1})$ for some non-negative integer $a$.

2. (ii)

   The base sampling step in Algorithm 2 should not be performed for elements $e\in V\setminus V^{\prime }$. As observed above, the set $V^{\prime }$ only gets revealed over time. Crucially, base sampling can be deferred: we sample an element $e\in V^{\prime }$ only upon the arrival of the first set $T_t$ containing it.

The algorithm, Net-Finder-V2, is given in Algorithm 3. First, we find the nearest power of $2$ which is larger than $N^{\prime }$ and define $\epsilon$ accordingly (line 3). Observe that the quantity $\alpha$ is a function of $\epsilon$ (as given in Theorem 7). The rest of the algorithm is essentially the same as Net-Finder-V1, but we perform base sampling on an element only when the first set containing it arrives. Thus, we classify the elements in $V$ as being either fresh or stale; initially, each element is fresh. An element becomes stale when we encounter the first set containing it. The alteration steps are then done exactly as in Net-Finder-V1. It follows that the statement of Theorem 7 holds for this algorithm as well.

We now describe the online hitting set algorithm combining Algorithm 1 and Algorithm 3. If $𝒜$ is an online algorithm for fractional hitting set and $ℐ=(U,ℱ)$ an instance of the online hitting set, we use Algorithm 1 to obtain the instance $𝒥=(V,𝒢)$, such that each set $S_t\in ℱ$ gives rise to set $T_t\in 𝒢$. In each iteration $t$, Net-Finder-V2 maintains $H$ as a valid hitting set for $𝒥$ by potentially adding elements from $T_t$. Then, we recover the corresponding hitting set for $ℐ$ by projecting the solution back, i.e., using the set $\text{proj}(H)$. We get the following result:

The idea of the algorithm is natural: we construct a nested family of sets starting with $V_0=V$, where each subsequent set $V_{\mathrm{\ell }+1}$ is a uniformly random subset of size roughly $(1/2+\delta )$ times that of the previous set $V_{\mathrm{\ell }}$, for a small “bias” term $\delta$. The process ends at a level $L^{\ast }$ with the corresponding set $V_{L^{\ast }}$ having size $\approx N/B$. If we chose $V_{L^{\ast }}$ as our hitting set $H$, the probability of each element $e\in H$ would be $\approx 1/B$, as desired. As sets in $𝒢$ are hit only with constant probability by $V_{L^{\ast }}$, we require “alterations” (backups) to ensure validity.

We assume that ${\phi }_{𝒢}$ that is $(a,b)$-well-behaved for some positive constants $a,b$. (Recall Definition 4.) Let $c_1$ be a large enough constant and assume $B\ge c_1$. For brevity, define

Now we can define the element levels as follows:

1. 1.

   Define $L^{\ast }$ to be the largest value $\mathrm{\ell }\in [0,\log B/c_1]$ such that

   $$h_{𝒢}(N_{\mathrm{\ell }},B_{\mathrm{\ell }})\stackrel{\text{(def.)}}{=}\sqrt{\frac{8\ln (B_{\mathrm{\ell }}\cdot \lceil \log N_{\mathrm{\ell }}\rceil \cdot {\phi }_{𝒢}(N_{\mathrm{\ell }},B_{\mathrm{\ell }}))}{B_{\mathrm{\ell }}}}\le 1/2.$$

   (3)

   If $L^{\ast }=0$ (or if $h_{𝒢}(N_0,B_0)>1/2$), we return $V$ as the hitting set. Since we have $L^{\ast }=\log \frac{B}{c_1}$ or $h_{𝒢}(N_{L^{\ast }},B_{L^{\ast }})>1/2$, it follows that

   $$\frac{1}{2^{L^{\ast }}}=O\left(\frac{1}{B}+\frac{\log \left(\log N\cdot B_{L^{\ast }}\cdot {\phi }_{𝒢}(N_{L^{\ast }},B_{L^{\ast }})\right)}{B}\right)=O\left(\frac{\log \left(\log N\cdot B_{L^{\ast }}\cdot {\phi }_{𝒢}(N_{L^{\ast }},B_{L^{\ast }})\right)}{B}\right).$$

   (4)

2. 2.

   Define $V_0=V$. For each $\mathrm{\ell }\in \{0,1,\mathrm{\dots },L^{\ast }-1\}$, let $V_{\mathrm{\ell }+1}$ be a random subset of $V_{\mathrm{\ell }}$ of size

   $$|V_{\mathrm{\ell }}|\cdot (1/2+h_{𝒢}(|V_{\mathrm{\ell }}|,B_{\mathrm{\ell }})).$$

3. 3.

   The level of element $e$ is defined as the largest $\mathrm{\ell }\in \{0,1,\mathrm{\dots },L^{\ast }\}$ such that $e\in V_{\mathrm{\ell }}$.

Since the elements of $V$ are given up-front, we define subsets $V_{\mathrm{\ell }}$ before sets in $𝒢$ arrive.

Given the notion of element levels, the main idea of the algorithm of [8], is the following: for each set $T\in 𝒢$, consider the first level where $|T\cap V_{\mathrm{\ell }}|$ is smaller than $B/2^{\mathrm{\ell }}$. If this (low-probability) bad event happens, we pick some element in $T$ at level $\mathrm{\ell }-1$ to hit it (since $|T\cap V_0|=|T|\ge B$, $\mathrm{\ell }>0$). The choice of this “backup” element is done consistently so that no element is chosen with too high a probability – showing such backup elements can be chosen is precisely where the small SCC of set system plays a role.

The algorithm (presented in 4) follows this outline: For each arriving set $T$ of size at least $B$, and each level $\mathrm{\ell }$, we define a backup element, namely ${\gamma }_{\mathrm{\ell }}(T)$, that will hit it in case of the bad event happening at the next level. This bad event at level $\mathrm{\ell }$ is that the size of $T\cap V_{\mathrm{\ell }}$ is smaller than $B/2^{\mathrm{\ell }}$. Since each arriving set $T$ is of size at least $B$, it either experiences a bad event at some level $\{0,1,\mathrm{\dots },L^{\ast }-1\}$, or intersects the final set $V_{L^{\ast }}$. It is now easy to check that the solution returned by the algorithm is feasible; the remaining part is to show that each element belongs to this hitting set with probability $\alpha /B$ for some suitable parameter $\alpha$.

In order to implement this algorithm in an online fashion, we need to define the backup element in line 4 in an online fashion; we do this in the next section with only a small loss in performance over the offline setting.

The next lemma defines a good backup map that can be maintained online:

To bound the probability of selecting an element $e$ in the hitting set constructed by Algorithm 4, we first relate $h_{𝒢}(N_{\mathrm{\ell }},B_{\mathrm{\ell }})$ for varying values of $\mathrm{\ell }$ (See [6] for the proofs).

We now combine Algorithm 1 and Algorithm 4 to get an online weighted hitting set algorithm. We first give a simple observation about Algorithm 1 (See [6] for the proof).

The online weighted hitting set algorithm is as follows: Algorithm 1 (with the changes in Claim 15) takes an instance $ℐ=(U,ℱ)$ of the weighted hitting set problem and outputs an online instance $𝒥=(V,𝒢)$ (which has the properties stated in Theorem 6). Since the backup maps ${\gamma }_{\mathrm{\ell }}$ can be defined in an online manner, Algorithm 4 can be implemented on the instance $𝒥$ in an online manner. This gives us an online hitting set $H$. The hitting set for $ℐ$ is just $\text{proj}(H)$. We now state the main result about the competitive ratio of this algorithm.