Online Disjoint Set Covers: Randomization Is Not Necessary

We use $\text{Opt}(E)$ to denote the maximum number of disjoint set covers of a hypergraph $G=(V,E)$. This value is also called cover-decomposition number [6]. We denote the minimum degree of the hypergraph $G=(V,E)$ as $\delta (E)\triangleq {\min }_{i\in V}|S\in E:i\in S|$. Note that trivially $\text{Opt}(E)⩽\delta (E)$. While this bound may not be tight (cf. Subsection 1.4), $\delta (E)$ serves as a natural benchmark for approximation and online algorithms.

An $O(\log n)$-approximation algorithm for the offline DSC problem [21] can be obtained by coloring each hyperedge with a color chosen uniformly at random from the palette of $\mathrm{\Theta }(\delta (E)/\log n)$ colors. To analyze this approach, we focus on a single node $i\in V$. We say that node $i$ gathers color $r$ if $i$ is contained in a hyperedge colored with $r$. Since node $i$ is contained in at least $\delta (E)$ hyperedges, and there are $\mathrm{\Theta }(\delta (E)/\log n)$ available colors, $i$ gathers all palette colors with high probability. By the union bound, this property holds for all nodes, i.e., all $\mathrm{\Theta }(\delta (E)/\log n)$ colors are fully used by an algorithm (also with high probability). Since $\text{Opt}(E)⩽\delta (E)$, the approximation ratio of $O(\log n)$ follows.

The hyperedges can be processed in a fixed order, and the random choice of a color can be replaced by the deterministic one by a simple application of the method of conditional probabilities [21, 3].

We say that Alg is (non-strictly) $c$-competitive if there exists $\beta ⩾0$ such that

While $\beta$ can be a function of $n$, it cannot depend on the input sequence $E$. If (1) holds with $\beta =0$, the algorithm is strictly $c$-competitive.

For randomized algorithms, we replace $\text{Alg}(E)$ with its expected value taken over the random choices of the algorithm.

The current best randomized algorithm was given by Emek et al. [14]; it achieves the (strict) competitive ratio of $O({\log }^{2}n)$. The general idea of their algorithm is as follows. To color a hyperedge $S$, their algorithm first computes the minimum degree ${\delta }^{\ast }$ of a node from $S$. By a combinatorial argument, they show that they can temporarily assume that $\delta (E)=O(n\cdot {\delta }^{\ast })$. Their algorithm then chooses $\mathrm{\ell }$ uniformly at random from the set $\{{\delta }^{\ast },2{\delta }^{\ast },4{\delta }^{\ast },\mathrm{\dots },2^{\log n}\cdot {\delta }^{\ast }\}$; with probability $\mathrm{\Omega }(1/\log n)$ such $\mathrm{\ell }$ is a 2-approximation of $\delta (E)$. Finally, to color $S$, it chooses a color uniformly at random from the palette of $\mathrm{\Theta }(\mathrm{\ell }/{\log }^{2}n)$ colors, using the arguments similar to those in the offline case.

We refrain from discussing it further here, as we present a variant of their algorithm, called Rand, in Subsection 2.1 (along with a description of the differences from their algorithm).

The best lower bound for the (strict and non-strict) competitive ratio of a randomized algorithm is $\mathrm{\Omega }(\log n/\log \log n)$ [14]; it improves on an earlier bound of $\mathrm{\Omega }(\sqrt{\log n})$ by Pananjady et al. [20].

The deterministic case is well understood if we restrict our attention to strict competitive ratios. In such a case the lower bound is $\mathrm{\Omega }(n)$ [20]. The asymptotically matching upper bound $O(n)$ is achieved by a simple greedy algorithm [14].

On the other hand, the current best lower bound for the non-strict deterministic competitive ratio is $\mathrm{\Omega }(\log n/\log \log n)$ [14].³³3This discrepancy in achievable strict and non-strict competitive ratios is quite common for many maximization problems: the non-strict competitive ratio allows the algorithm to have zero gain on very short sequences, thus avoiding initial choices that would be bad in the long run. The $O(n)$ upper bound of [14] clearly holds also in the non-strict setting, but no better algorithm has been known so far.

Unlike approximation algorithms, derandomization is extremely rare in online algorithms.⁴⁴4Many online problems (e.g., caching [23, 1] or metrical task systems [7, 8, 9]) exhibit a provable exponential discrepancy between the performance of the best randomized and deterministic algorithms. For many other problems, the best known deterministic algorithms are quite different (and more complex) than randomized ones. To understand the difficulty, consider the standard (offline) method of conditional probabilities [3] applied to the offline DSC problem: the resulting algorithm considers all the random choices (color assignments) it could make for a given hyperedge $S$, and computes the probability that future random choices, conditioned on the current one, will lead to the desired solution. Choosing the color that maximizes this probability ensures that the probability of reaching the desired solution does not decrease as subsequent hyperedges are processed. In some cases, exact computations are not possible, but the algorithm can instead estimate this probability by computing a so-called pessimistic estimator [22]. This is not feasible in the online setting, since an algorithm does not know the future hyperedges, and thus cannot even estimate these probabilities.⁵⁵5As observed by Pananjady et al. [20], however, these probabilities can be estimated if an online algorithm knows the final min-degree $\delta (E)$ in advance, which would lead to an $O(\log n)$-competitive algorithm for this semi-offline scenario.

Rand is closely related to the randomized algorithm by Emek et al. [14]. The main difference is that the phases of the nodes in their algorithm are of fixed lengths, being powers of $2$.⁶⁶6The pseudocode of their algorithm does not use phases, but with some fiddling with constants, it can be transformed into one that does. They use probabilistic arguments to argue that with high probability each node gathers $q_k$ colors in a phase of length $\mathrm{\Theta }(2^k\cdot {\log }^{2}n)$. Instead, we treat the number of colors gathered in a phase as a hard constraint (we require that each node gathers $q_k$ of them), and instead the phase lengths of the nodes become random variables. As it turns out, this subtle difference allows us to derandomize the algorithm.

Another small difference concerns the color selection. While Rand chooses the color uniformly at random from the set $R_{k^{\ast }}$, the algorithm of [14] would choose it from the set ${\uplus }_{j=0}^{k^{\ast }}{R}_j$. This difference affects only the constant factors of the analysis.

As mentioned earlier, the gain of Rand is directly ensured by the algorithm definition provided that each node has completed some number of phases.

Note that $q_k$ is slightly less than $|R_k|=2^k$; this gives a better bound on the the expected phase lengths, while still ensuring that if all nodes completed phase $\mathrm{\ell }$, they gathered at least $2^{\mathrm{\ell }-1}$ common colors.

In phase $\mathrm{\ell }$, each node gathers at least $q_{\mathrm{\ell }}$ colors from the palette $R_{\mathrm{\ell }}$, i.e., all colors from $R_{\mathrm{\ell }}$ except at most $|R_{\mathrm{\ell }}|-q_{\mathrm{\ell }}⩽2^{\mathrm{\ell }}/(2n)$ colors. Thus, all nodes share at least $|R_{\mathrm{\ell }}|-n\cdot (2^{\mathrm{\ell }}/(2n))=2^{\mathrm{\ell }-1}$ common colors from $R_{\mathrm{\ell }}$, i.e., Rand fully uses at least $2^{\mathrm{\ell }-1}$ colors. $◀$

Note that we could sum the above bound over all phases completed by all nodes, but this would not change the asymptotic gain.

The above lemma points us to the goal: to show that for an input $E$ with a sufficiently large $\delta (E)$, each node completes an appropriately large number of phases. In Subsection 2.3, we show that if $\delta (E)=\mathrm{\Omega }(2^{\mathrm{\ell }}\cdot {\log }^{2}n)$, then each node completes $\mathrm{\ell }$ phases, provided a certain random event ${𝒯}_E$ occurs.

The first step is to identify the variables to control. Natural choices are the node degrees and the number of colors gathered so far by each node.

For this purpose, we define $c_{ik}=|C_{ik}|$ for each node $i$ and each phase $k⩾0$.

We also introduce counters $w_{ik}$, which are initially set to zero. Recall that whenever a new hyperedge $S$ containing node $i$ arrives, Rand computes $p_S={\min }_{i\in S}p(i)$. For each node $i\in S$ such that $p(i)⩽p_S+h-1$, we increment the counter $w_{i,p(i)}$. Note that these $w_{i,p(i)}$ variables are incremented exactly for nodes $i$ for which there is a non-zero probability of increasing their set of colors $C_{i,p(i)}$ (as then a random integer $k^{\ast }$ chosen by Rand has a non-zero chance of being equal to $p(i)$).

By the definition of $w_{ik}$, at each step ${\sum }_{k⩾0}{w}_{ik}⩽\mathrm{deg}(i)$. While these quantities are not necessarily equal, we will treat ${\sum }_{k⩾0}{w}_{ik}$ as a good proxy for $\mathrm{deg}(i)$ and deal with the discrepancy between these two quantities later.

Now we want to introduce an expression that links ${\sum }_{k⩾0}{w}_{ik}$ (the proxy for degree) with ${\sum }_{k⩾0}{c}_{ik}$ (the number of colors gathered) for a node $i$. A simple difference of these two terms does not make sense: the expected growth of $c_{ik}$ varies over time, since it is easier to gather new colors when $c_{ik}$ is small. This effect has been studied in the context of the coupon collector’s problem [19]. To overcome this issue, we introduce the following function, defined for each integer $k⩾0$:

Note that in a process of choosing random colors from palette $R_k$ of $2^k$ colors, the expected number of steps till $m$ different colors are gathered is $d_k(m)/h$.

Now we focus on a single node $i$ in phase $p(i)$. We consider a sequence of hyperedges $S$ containing node $i$, neglecting those hyperedges $S$ for which $p(i)⩾p_S+h$. That is, all considered hyperedges increment the counter $w_{i,p(i)}$. Then, the value of $d_k(c_{i,p(i)})$ corresponds to the expected number of such hyperedges needed to gather $c_{i,p(i)}$ colors from the palette $R_{p(i)}$. We can thus use the expression ${\sum }_{k⩾0}(w_{ik}-2\cdot d_k(c_{ik}))$ to measure the progress of node $i$: small values of this expression indicate that it is gathering colors quite fast, while large values indicate that it is falling behind. Note that since $c_{ik}⩽q_k⩽2^k$, the value of $d_k(c_{ik})$ is always well defined.

We note that the previous applications of the potential function method [2, 5, 10, 18] did not require such transformations of variables: in their case, the potential function was used to guide deterministic rounding: the function $\mathrm{\Phi }$ directly compared the cost (or gain) of a deterministic algorithm with that of an online fractional solution. Instead, our solution operates directly on the input, without the need to generate a fractional solution first.

Using the random choices of Rand, we can argue that in expectation the value of $Z_i^{\ast }\triangleq {\sum }_{k⩾0}(w_{ik}-2\cdot d_k(c_{ik}))$ is decreasing in time. However, to argue that $\exp (Z_i^{\ast })$ is also decreasing in expectation, we would have to ensure that $Z_i^{\ast }$ is upper-bounded by a small constant (and use the fact that $\exp (x)$ can be approximated by a linear function for small $x$).

In the previous papers [2, 5, 10, 18], this property was achieved by scaling down $Z^{\ast }$ by the value of Opt. An algorithm was then either given an upper bound on Opt (in the case of the throughput maximization of the virtual circuit routing [10]) or Opt was estimated by standard doubling techniques (in the case of the cost minimization for set cover variants [2, 5, 18]). In the latter case, the algorithm was restarted each time the estimate on Opt was doubled. Unfortunately, the DSC problem (which is an unbounded-gain maximization problem) does not fall into any of the above categories, and the doubling approach does not seem to work here.

Instead, we replace the scaling with a weighted average. That is, for each node $i$, we define

and the potential as

Note that all counters and variables defined above are random variables; they depend on particular random choices of Rand. We use $p^t(i)$, ${\mathrm{deg}}^t(i)$, $w_{ik}^t$, $c_{ik}^t$, $Z_i^t$ and ${\mathrm{\Phi }}^t$ to denote the values of the corresponding variables at the end of step $t$ of the algorithm (after Rand has processed the hyperedge presented in step $t$). The value of $t=0$ corresponds to the state of these variables at the beginning of the algorithm; note that $p^0(i)={\mathrm{deg}}^0(i)=w_{ik}^0=c_{ik}^0=Z_i^0=0$ for all $i$ and $k$. Therefore,

For an input instance $E$ consisting of $T$ steps, we define a random event ${𝒯}_E$ that occurs if ${\mathrm{\Phi }}^t⩽n$ for each step $t\in \{0,\mathrm{\dots },T\}$ of Rand execution on input $E$.

Let $r\triangleq 24h\cdot \ln (4\mathrm{e}\cdot n)$. We consider two cases.

• $\mathrm{■}$

  First, we assume that $\delta (E)>r$. Then we can find an integer $\mathrm{\ell }⩾0$ such that . By Lemma 2, each node then completes its phase $\mathrm{\ell }$, and so by Lemma 1, $\text{Rand}(E)⩾2^{\mathrm{\ell }-1}⩾\delta (E)/(4r)$.

• $\mathrm{■}$

  Second, we assume that $\delta (E)⩽r$. Trivially, $\text{Rand}(E)⩾0⩾(\delta (E)-r)/(4r)$.

In both cases, $\text{Rand}(E)⩾(\delta (E)-r)/(4r)⩾\text{Opt}(E)/(4r)-1/4$. $◀$

As described above, Det guarantees that ${\mathrm{\Phi }}^t⩽n$ for each step $t\in \{0,\mathrm{\dots },T\}$, i.e., ${𝒯}_E$ occurs. Note that Lemma 3 lower-bounds the gain of Rand in every execution conditioned on ${𝒯}_E$, and Det can be seen as such an execution. Therefore, the bound of Lemma 3 can be applied, yielding

i.e., the competitive ratio of Det is at most $96\cdot h\cdot \ln (4\mathrm{e}\cdot n)=O({\log }^{2}n)$.

Note that, by the lower bounds of [20, 14], an additive term (in our case equal to $1/4$) is inevitable for obtaining a sub-linear competitive ratio. $◀$