Online Disjoint Set Covers: Randomization is not Necessary
Marcin Bienkowski Jarosław Byrka Łukasz Jeż

Casimir energy on the sphere and 6D CFT trace anomaly
    R Aros^1, F Bugini^2, DE Díaz^3 and C Núñez-Barra^4
    
=======================================================




T1lmrmscit<->ssub * lmr/m/scsl





In the online disjoint set covers problem, the edges of a hypergraph are
revealed online, and the goal is to partition them into a maximum number of
disjoint set covers. That is, n nodes of a hypergraph are given at the
beginning, and then a sequence of hyperedges (subsets of [n]) is presented to
an algorithm. For each hyperedge, an online algorithm must assign a color (an
integer). Once an input terminates, the gain of the algorithm is the number of
colors that correspond to valid set covers (i.e., the union of hyperedges that
have that color contains all n nodes).

We present a deterministic online algorithm that is O(log^2 n)-competitive,
exponentially improving on the previous bound of O(n) and matching the
performance of the best randomized algorithm by Emek et al. [ESA 2019].

For color selection, our algorithm uses a novel potential function, which can be
seen as an online counterpart of the derandomization method of conditional
probabilities and pessimistic estimators. There are only a few cases where 
derandomization has been successfully used in the field of online algorithms. In
contrast to previous approaches, our result extends this tool to tackle the
following new challenges: (i) the potential function derandomizes not only the
Chernoff bound, but also the coupon collector's problem, (ii) the value of of the maximization problem is not bounded a priori, and (iii) we do not produce
a fractional solution first, but work directly on the input. 








§ INTRODUCTION


In this paper, we study online algorithms for maximizing the number of set
covers of a set of nodes. We focus on a hypergraph (set system) G = (V,E) that has
n = |V| nodes and where each hyperedge S ∈ E is a subset of nodes from
V. A subset E' ⊆ E is called set cover if ⋃_S ∈ E'
S = V, i.e., every node is covered by at least one hyperedge of E'. In the
disjoint set covers (DSC) problem <cit.>, the goal is to
partition the set of hyperedges E into maximum number of mutually
disjoint subsets E = E_1 ⊎ E_2 ⊎…⊎ E_k, where 
each E_j is a set cover. Note that E is a multi-set, i.e., it can contain
multiple copies of the same hyperedge.

The problem has been studied in a theoretical setting, but as we discuss later, it
also finds applications in energy minimization in sensor
networks <cit.>. 



    Coloring Perspective.


When constructing a solution to the DSC problem, it is convenient to think in
terms of coloring hyperedges.[The DSC problem should not be confused
with the hyperedge coloring problem, which requires that the hyperedges of the same 
color are disjoint.] Each color corresponds then to a subset of hyperedges
that have that color, and the color is fully used if the hyperedges
colored with it form a set cover. The problem then becomes equivalent to
coloring hyperedges, so that the number of fully used colors is maximized.



    Online Variant.


In this paper, we focus on the online variant of the DSC problem, where
the set V is given in advance, but the hyperedges of E arrive in an online
fashion. Once a hyperedge S ∈ E arrives, it must be colored immediately and
irrevocably. Again, the goal is to maximize the number of fully used colors. The
performance of an online algorithm is measured by the competitive ratio, i.e.,
the ratio of the number of fully used colors produced by the optimal
offline algorithm  to that of an online algorithm .




    Our Contribution.


We present a deterministic online O(log^2 n)-competitive algorithm for
the DSC problem, which improves exponentially over the O(n)-competitive algorithm by
Emek et al. <cit.>, and matches the performance of their randomized
algorithm <cit.>.

Our algorithm is based on a novel potential function that guides the choice of
colors. As we discuss later in <ref>, our approach can be seen as 
an online-computable counterpart of the method of conditional probabilities that
simultaneously controls the derandomization of the Chernoff bound and the coupon
collector's problem. 




 §.§ Offline Scenario: Previous Results



The disjoint sets cover problem is known to be NP-complete <cit.>, can
be approximated within a factor of (1+o(1)) ·ln |V| <cit.> and
cannot be approximated within a factor of (1-) ·ln |V| for any
> 0 unless ⊆(n^loglog
n) <cit.>.[The authors of <cit.> 
call this problem set cover packing or one-sided domatic problem.]



    OPT vs. Min-degree.


We use (E) to denote the maximum number of disjoint set covers of a
hypergraph G=(V,E). This value is also called cover-decomposition
number <cit.>. We denote the minimum degree of the hypergraph 
G=(V,E) as δ(E) ≜min_i ∈ V |S ∈ E  i ∈ S|.
Note that trivially (E) ≥δ(E). While this bound may not be tight
(cf. <ref>), δ(E) serves as a natural benchmark for
approximation and online algorithms.



    Random Coloring and its Straightforward Derandomization.


An O(log n)-approximation algorithm for the offline DSC
problem <cit.> can be obtained by coloring each hyperedge with a color
chosen uniformly at random from the palette of Θ(δ(E) / log
n) colors. To analyze this approach, focus on a single node i ∈ V. We say
that node i gathers color r if i is incident to a hyperedge colored
with r. Since node i is contained in (v) ≥δ(E) hyperedges,
and there are Θ(δ(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 Θ(δ(E) / log n) colors are fully used by
an algorithm (also with high probability). Since (E) ≤δ(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 use of the
method of conditional probabilities <cit.>.




 §.§ Online scenario: previous results



In the online case, the edges of E are revealed sequentially. For notational
convenience, we use E to denote both the set and a sequence of hyperedges (the
input). We use (E) to denote the number of fully used colors in the
solution of an online algorithm .



    Competitive Ratio and Additive Term.


We say that  is c-competitive if there exists 
β such that 

    (E) ≥(E)  /  c - β.

While β can be a function of n, it cannot depend on the input sequence
E. For randomized algorithms, we replace (E) with its expected value taken
over the random choices of the algorithm.

We note that the use of the additive constant β is typical in the
literature on online algorithms <cit.> for problems where the value of
can be arbitrarily large. The additive term is unavoidable for the DSC
problem: setting β = 0 makes the competitive ratio of any deterministic
algorithm to be Ω(n) <cit.>. On the positive side, the
parameter β used in our analysis is merely 1/4.




    Randomized Algorithms.


The currently best randomized algorithm was given by Emek et
al. <cit.>; it achieves the competitive ratio of O(log^2 n). To
understand its main idea, consider a straightforward adaptation of the
randomized offline algorithm outlined in <ref> to the
online setting: assume that to color a hyperedge S, it chooses a random color
from the palette of Θ(δ^* / log n) colors, where δ^* is
the current minimum degree of the hypergraph.

This idea would fail because there may be many nodes in S whose current degree
is much larger than γ^*, and such nodes may already have many or all of
the colors from the palette. Such an algorithm would then make a slow progress
in coloring these nodes. To alleviate this problem, an algorithm can use an
infinite number of disjoint palettes, indexed by integers, with palette k
containing Θ(2^k/log n) colors. To color S, an algorithm first
randomly chooses a palette index k from {logγ^*, …,
logγ^* + log n}, and then uses a color randomly picked from the
palette k. While the randomized algorithm of Emek et al. <cit.> is
more sophisticated, it builds on this idea, losing the first factor of O(log
n) in palette selection, and the second factor of O(log n) in the same place
as the offline algorithm does. 

The best (randomized) lower bound is Ω(log n / loglog
n) <cit.>; it improves on an earlier bound of Ω(√(log
n)) by Pananjady et al. <cit.>.



    Deterministic Algorithms.


The deterministic case is much less understood: while the randomized lower bound
of Ω(log n / loglog n) holds for deterministic algorithms, the best
upper bound is O(n) and is achieved by a simple greedy
algorithm <cit.>. The known results are summarized in
<ref>.






 §.§ Our Results and Technical Challenges



In our paper, we present a deterministic online algorithm that is O(log^2
n)-competitive, an exponential improvement over the previous bound of O(n).
To some extent, our algorithm can be seen as a derandomization of 
an algorithm by Emek et al. <cit.>. 



    General Derandomization Tools.


Unlike approximation algorithms, the derandomization is extremely rare in online
algorithms.[Many online problems (e.g., caching <cit.>
or metrical task systems <cit.>) exhibit 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 <cit.> 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 estimate this probability instead by computing the amount called
pessimistic estimator <cit.>). This is infeasible in the online
setting, since an algorithm does not know the future sets, and thus cannot even
estimate these probabilities.[As observed by Pananjady et
al. <cit.>, however, these probabilities can be estimated if an online
algorithm knows the final min-degree δ(E) in advance, which
would lead to an O(log n)-competitive algorithm for this semi-offline
scenario. As pointed out by Emek et al. <cit.>, this approach relies
heavily on the knowledge of δ(E).]



    Online-Computable Potential Functions.


In the realm of online algorithms, the method of conditional probabilities has
been successfully replaced several times by an online-computable potential
function that guides the choice of the deterministic
algorithm <cit.>.[They should not
be confused with the ubiquitous “standard” potential functions that link the
states of online and offline algorithms and which are used only in the
analysis.] 

To illustrate this concept, let c_i be the number of colors that node i
gathered so far. We use (i) to denote the current degree of node
i. The ideas from previous papers would then suggest choosing a potential
function of the form Φ = ∑_i ∈ [n]exp(z_i), where z_i = (i) -
γ· c_i for some constant γ. Note that Φ relates the
resources expended by an algorithm (growth of the degree) to its progress
(number of gathered colors). We will show issues with this choice of Φ
later, but first we highlight its advantages.

Since initially z_i = 0 for each node i, at the beginning we have Φ =
n. The core of the method is to show that, for each considered hyperedge S,
it is possible to choose its color, so that Φ does not increase. This is
usually achieved by the probabilistic argument: by showing that a random
choice of a color would lead to an expected decrease of Φ. This
would guarantee that Φ≤ n, which would imply that z_i ≤ln n for
each i. Hence, c_i could be lower-bounded with respect to (i)
for each node. If the colors are chosen from a fixed palette
(cf. <ref>), they are used by all nodes, and thus
correspond to valid set covers. This process can be seen as a derandomization of
the Chernoff bound / high probability argument.




    Technical Challenges.


As we discuss below, the ideas from the previous works cannot be directly
applied to the DSC problem, and we need to introduce several new techniques.

The first problem is that setting z_i = (i) - γ· c_i disregards
the fact that the rate of gathering new colors (by a random process)
decreases as c_i grows. This effect has been studied in the context of the
coupon collector's problem <cit.>. To overcome this issue, we need to
replace γ· c_i with an appropriate function of c_i. We note that
this problem was not present in the previous applications of the potential
function method <cit.>. In their case, the
potential function was used to guide deterministic rounding: the
function Φ 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.

The second problem is that the expected decrease in Φ requires that that
the values of exp(z_i) are decreasing (at least on the average), while a
simple argument shows that only the variables z_i are decreasing. In the
previous papers, the connection between z_i and exp(z_i) was made by
ensuring that the variables z_i are universally upper-bounded: this can be
achieved by first dividing them by the value of . An algorithm was then
either given an upper bound on (in the case of the throughput maximization
of the virtual circuit routing <cit.>) or was estimated by
standard doubling techniques (in the case of the cost minimization for set cover
variants <cit.>). In the latter case, the algorithm
was restarted each time the estimate on was doubled.

The DSC problem (which is an unbounded-gain maximization problem) does not fall
into any of the above categories. Moreover, the currently best randomized
algorithm <cit.> suggests that instead of focusing on the global optimum
(or the current minimum degree), each node should rather gather colors at a rate
depending on its own degree. To deal with node degrees growing in time,
we partition the steps of each node into phases. In each phase, we look at the
fraction whose numerator corresponds to the growth of z_i and whose
denominator corresponds to the current approximate node degree. The resulting
potential for a node (see <ref>) is a weighted average of
these fractions. 




 §.§ Related Work



An application of the DSC problem arises in a sensor network, where each node
corresponds to a monitoring target and each hyperedge corresponds to a sensor
that can monitor a set of targets. At any given time, all targets need to be
monitored. A possible battery-saving strategy is to partition the sensors into
disjoint groups (each group covering all targets) and activate only one group at
a time, while the other sensors remain in a low-power mode <cit.>. 

If the assumption that each sensor can participate only in a single group is
dropped, this leads to more general sensor coverage problems. The goal is then
to maximize the lifetime of the network of sensors while maintaining the
coverage of all targets. The offline variants of this problem have been studied
both in general graphs <cit.> and in geometric
settings <cit.>.

Another line of work studied the relationship between the minimum degree δ(E)
and the cover-decomposition number (E). Trivially, δ(E)/(E) ≥
1. This ratio is constant if G is a graph <cit.>, and it is at most
O(log n) for every hypergraph <cit.>; the latter bound is
asymptotically tight <cit.>. Interestingly enough, all the known papers
on the DSC problem (including ours) relate the number of disjoint set covers to
δ(E). It is an open question whether our estimate of the competitive
ratio is tight: it could potentially be improved by relating the gain of an
algorithm directly to (E) instead of δ(E).





 §.§ Preliminaries


An input to our problem is a gradually revealed hypergraph G=(V,E). V
consists of n nodes numbered from 1 to n, i.e., V = [n]. The set E of
hyperedges is presented one by one: in a step t, an algorithm learns S_t ∈
E, where S_t ⊆ [n], and has to color it. We say that node i gathers
color r if i is incident to a hyperedge colored with r. We say that
a color r is fully used if all nodes have gathered it. The objective of
an algorithm is to maximize the number of fully used colors. 

At any point in time, the degree of a node j is the current
number of hyperedges containing j. Let δ(E) = min_i ∈ [n] |{ S_t
∈ E : v_i ∈ S_t }|, i.e., δ(E) is the minimum degree of G at the
end of the input E. Clearly, (E) ≤δ(E).






§ OUR DETERMINISTIC SOLUTION


We first describe our phase-based framework (cf. <ref>). Then, we
introduce the potential function that guides the choice of colors
(cf. <ref>). 



 §.§ Partitioning Steps into Phases



We start with some notions, defined for each integer k ≥ 1:

    b_k    ≜ 2^k-1,    
        B_k    ≜∑_j=1^k b_j = 2^k - 1, 
    
        t_k    ≜⌈* 1 - 1/2n· b_k ⌉,    
        R_k    ≜{B_k-1+1, …, B_k}.

Note that |R_k| = b_k. 

For each hyperedge S ∈ E, chooses a color r: this causes all nodes from
S to gather color r. However, in our analysis (and even in the algorithm
description), we ignore some of these colors. 

For each node i independently,  maintains its phase p(i),
initially set to 1. In each step, the sole focus of the node i is to gather
colors from the palette R_p(i). We use c_ik to denote the number of
colors from palette R_k that node i has gathered so far, while it has been
within phase k. That is, for a node i, we increment the counter
c_i,p(i) when node i gathers a new color from R_p(i) and we never change
the counter c_ik for k ≠ p(i). Clearly, c_ik is a lower bound on the
number of colors from palette R_k gathered by node i so far.

A phase k for node i terminates when it has gathered t_k colors from palette
R_k. In such case, node i increments its phase number p(i) in the next
step. Note that t_k is slightly smaller than |R_k| = b_k; as we argue later
this helps us speed up the process without changing the asymptotic number of
fully used colors.

For each node i and an integer k ≥ 1, we maintain two counters w_ik
and w^*_ik; all these counters are initially set to zero. Whenever a new
hyperedge containing node i arrives, we increment either w_i,p(i) or
w^*_i,p(i) (we describe this choice later). 



    ∑_k ≥ 1 (w_ik + w^*_ik) is always equal to the current degree
    of node i. Furthermore, c_ik = w_ik = w^*_ik = 0 for every node i
    and k > p(i).




 §.§ Choosing Colors with Potential Function



We now introduce further notions, defined for each integer k ≥ 1:

    h    ≜log n , 
    α_k(j)    ≜1/h·b_k - j + 1/b_k, 
                  (defined for every j)
    
        d_k(ℓ)    ≜∑_j=1^ℓ1/α_k(j), 
                  (defined for every ℓ≤ b_k)

Finally, for each node i and each integer k ≥ 1, we define 

    z_ik≜ 
            w_ik - 2 · d_k(c_ik).

Note that since c_ik≤ t_k ≤ b_k, the value of d_k(c_ik) is always
well defined. 

Recall that, for each node i and within phase k, the growth of its degree is
w_ik + w^*_ik, while c_ik is the number of colors gathered from the
palette R_k. Thus, neglecting w^*_ik, the value of z_ik relates these
amounts. As mentioned in <ref>, a direct comparison of
w_ik and c_ik makes no sense. So instead of c_ik we thus use
d_k(c_ik), which corresponds to the expected number of steps in the random
process of collecting colors from the palette R_k until c_ik distinct
colors are found.

Negative values of z_ik indicate that node i is gathering colors in phase
k faster than the benchmark, while positive values indicate that it is falling
behind. Our algorithm will choose a color in such a way that z_ik's are
appropriately upper-bounded. To this end, we define the potential for each node
i as

    Φ_i≜exp( ∑_k ≥ 1z_ik/4 h · b_k),

and the total potential as

    Φ≜∑_i ∈ [n]Φ_i.


Now describe the behavior of in a single step, when a hyperedge S
appears. Let p(i) denote the phase of node i before S appears and let
= min_i ∈ S p(i). For each node i ∈ S, 

    
  * increments w_i,p(i) if i ≤ + h - 1, and 
    
  * increments w^*_i,p(i) if i ≥ + h.

To color S, takes the color from the set 

    _≤ k ≤+h-1 R_k
 
resulting in a minimum value of potential Φ.

Since the number of colors to consider is bounded by a polynomial in n and the
number of sets in the input, can be implemented in polynomial time.







§ ANALYSIS ROADMAP



To compute the competitive ratio of , we need to link (E) to
δ(E) for each input E. We start by estimating the former.



    If each node has completed at least ℓ phases, 
    then (E) ≥ b_ℓ / 2.



    In phase ℓ, each node gathers at least t_ℓ colors from the palette
    R_ℓ, i.e., all colors from R_ℓ except at most |R_ℓ|
    - t_ℓ≤ b_ℓ / (2n) colors. So all nodes share at least
    |R_ℓ| - n · (b_ℓ / (2n)) ≥ b_ℓ / 2 common colors from
    R_ℓ, i.e.,  fully uses at least b_ℓ / 2 colors.


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



    Upper Bound on Node Degrees.


The hard part of our analysis is to appropriately upper-bound
the values of w_ik and w^*_ik, i.e., to show the following two lemmas.

lemmastepsbound
    
    Fix a node i and an integer ℓ≥ 1. At any time, it holds that 
    ∑_k=1^ℓ w_ik≤ 8 h · b_ℓ·ln(4· n).


lemmawstarbound
    
    Fix a node i and an integer ℓ≥ 1. At any time, it holds that 
    ∑_k=1^ℓ w^*_ik≤ 16 h · b_ℓ·ln(4· n). 


As we already mentioned in <ref>, to estimate the growth of
w_ik (<ref>), we show that we can always control the
total potential. A simple computation shows that the initial potential is equal
to n. Furthermore, using a probabilistic method, we can show that can
always choose a color for a given hyperedge, so that the potential always
remains at most n (cf. <ref>). The bound on
Φ creates a connection between b_k and z_ik, and thus also between
b_k and w_ik, which allows us to prove <ref>
(cf. <ref>).

The growth of the variables w^*_ik is not controlled by the potential, but
by the definition of , they grow only for nodes whose degree is very high
compared to the current minimum degree. By constructing an appropriate charging
argument, we can link their growth to the growth of other variables w_ik
(cf. <ref>).





    Competitive Ratio.


Using the three lemmas above, we can relate the final minimum node
degree δ(E) to the number of phases each node has completed. This 
directly gives the competitive ratio of .



    Fix an integer ℓ≥ 1. If δ(E) > 24 h ·ln(4· n)
    · b_ℓ, then each node has completed at least ℓ phases.



    Suppose for a contradiction that there exists a node i
    for which p(i) ≤ℓ at the input end. We would then have
    
    δ(E) 
            ≤∑_k ≥ 1* w_ik + w^*_ik 
            = ∑_k=1^ℓ* w_ik + w^*_ik≤ 24 h ·ln(4· n) · b_ℓ,

    where the first two relations follow by <ref> and the 
    last one by <ref> and <ref>.
    This would contradict the assumption of the lemma.





    is O(log^2 n)-competitive

    

    Fix an input sequence  and let q ≜ 24 h ·ln(4· n).
    We consider two cases.
    
    
  * First, assume that δ(E) > q = q · b_1. Then we can find an
        integer ℓ≥ 1 such that q · b_ℓ < δ(E) ≤ q ·
        b_ℓ+1. By <ref>, each node then completes
        at least ℓ phases, and so by <ref>, ()
        ≥ b_ℓ/2 = b_ℓ+1 / 4 ≥δ(E) / (4 · q).
    
  * Second, assume that δ(E) ≤ q. Trivially, () ≥ 0
        ≥ (δ(E) - q) / (4q).
    
    In both cases, 
    () ≥ (δ(E) - q) / (4q) ≥(E) / (4q) - 1/4. 
    i.e., the competitive ratio of is at most 4 · q = O(log^2 n). 
    
    Note that, by the lower bounds of <cit.>, an additive term
    (equal to 1/4 in our case) is inevitable for obtaining a sub-linear
    competitive ratio.









§ CONTROLLING THE POTENTIAL



In this section, we show that the potential Φ is always at most n.
A simple argument estimates its initial value.



Initially, the potential Φ is equal to n.



Initially, w_ik = c_ik = 0 for every node i and every integer k ≥ 1.
Thus, z_ik = 0, which implies Φ_i = ^0 = 1. So at the beginning,
Φ = ∑_i=1^n Φ_i = n.




    Random Experiment.


In this section, we use the probabilistic method to argue that there always exists a
color for the considered hyperedge, such that the resulting potential does not
increase. Since  always chooses a color that minimizes the potential, this
will imply that Φ is always at most n.

Recall how  chooses a color for a hyperedge S: it sets = min_i
∈ S p(i), where p(i) is the phase of node i before S appears. Next, it
takes the color from the set 

    ℛ≜_≤ k ≤+h-1 R_k
 
which results in a minimum value of the potential Φ.

We replace the above procedure with a random choice of a color from
ℛ and show that the resulting potential does not increase in
expectation. By the probabilistic method, this will imply that there
exists a deterministic choice of the color from ℛ that does not
increase the potential. 

To this end, we first choose a random integer k uniformly from the set {, +1, …,  + h - 1 }. Second, conditioned on the first
choice, we choose a random color uniformly from the set R_k.

Throughout this section, we focus on a single step, in which the hyperedge S is
processed. We use w_ik, c_ik, z_ik, and Φ_ik to denote the
values of the corresponding variables before S appears. We use w'_ik to
denote their values immediately after S appears (these variables depend only on S and
not on our random experiment). Furthermore, we use c'_ik, z'_ik, and
Φ'_ik to denote the random variables corresponding to
variables right after S is randomly colored. 

Whenever we write a relation involving a random variable and not its expectation
(e.g., z'_ik≤ z_ik), we mean that it holds for all realizations of that
random variable. 



    Analyzing Variables z.




    Fix a node i and an integer k ≥ 1. 
    If i ∉ S or k ≠ p(i), then z'_ik = z_ik.



    In this case, w'_ik = w_ik and c'_ik = c_ik by the definition of
    (it modifies only variables w_i,p(i) and c_i,p(i) and
    only for i ∈ S). The lemma follows by the definition 
    of z_ik.




    
    Fix a node i ∈ S and let p = p(i). If p ≥ + h, then
    z'_ip = z_ip.



    In the considered case, increments w^*_ip while leaving w_ip
    intact, i.e., w'_ip = w_ip. On the other hand, the random
    process never picks a color from R_p, and thus c'_ip =
    c_ip. The lemma follows by the definition of z_ip.




    
    Fix a node i ∈ S and let p = p(i). If p ≤ + h - 1, then
    
    z'_ip = z_ip + 1 + 
                -2/α_p(c_ip+1)    with probability α_p(c_ip+1),
    
                0    otherwise.




    By the definition of , we have p ≥. 
    Combining this with the 
    lemma assumption, we get p ∈, …,  + h - 1. 

    First, we analyze the relation between c'_ip and c_ip.
    Note that c'_ip = c_ip + 1 if node i gathers 
    a new color from R_p, and c'_ip = c_ip otherwise. 
    For a node i to gather a new color from R_p, 
    first the integer chosen randomly from the set
    {, …, +h-1} must be equal to p (which happens
    with probability 1/h). Second, conditioned on the former event, a color
    chosen randomly from the palette R_p must be different from all 
    c_ip colors from R_p gathered so far by node i (which
    happens with with the probability (|R_p|-c_ip)/|R_p| = (b_p-c_ip)/b_p). In summary,
    the probability of gathering a new color is (1/h) ·
    (b_p-c_ip)/b_p = α_p(c_ip+1).
    Hence,
    
    c'_ip =  
                c_ip + 1    with probability α_p(c_ip+1),
    
                c_ip   otherwise.

    Recall that d_k(ℓ) = ∑_j=1^ℓ 1 / α_k(j).
    Therefore, 
    
    d_p(c'_ip) - d_p(c_ip) = 
             
                1/α_p(c_ip+1) 
                   with probability α_p(c_ip+1),
    
                0    otherwise.

    Finally, in the considered case, w'_ip = w_ip + 1. 
    Since z_ik = w_ik - 2 · d_k(c_ik), 
    
    z'_ip - z_ip    = * w'_ip - w_ip - 2 ·* d_p(c'_ip) - d_p(c_ip) 
        = 1 + 
             
                -2/α_p(c_ip+1) 
                   with probability α_p(c_ip+1),
    
                0    otherwise.




For the next lemma, we need the following technical 
bound (proven in <ref>).

claimexpbound

    Fix ∈ [0,1], α∈ [, 1] and a real x.
    Let X be a random variable such that
    
    X = 
                x -  / α   with probability α,
    
                x    otherwise.

    Then, [^X] ≤^x-/2.





    Fix a node i ∈ S and let p = p(i). 
    Then,
    
    [exp*z'_ip/4h · b_p] 
            ≤exp*z_ip/4h · b_p.




    If p ≥ + h, then z'_ip = z_ip by
    <ref>, and the lemma follows trivially. So in the
    following, we assume that p ≤ + h - 1.

    Taking the guarantee of <ref> and dividing its both
    sides by 4 h · b_p, we get
    
    z'_ip/4h · b_p = z_ip + 1/4h · b_p + 
                -1/(2h · b_p ·α)    with probability α,
    
                0    otherwise.

    where α≜α_p(c_ip+1).
    
    Note that c_ip≤ t_p - 1 ≤ b_p -1 as otherwise phase p 
    of node i would have ended in an earlier step. 
    Hence, 
    
    α
                = 1/h·b_p - c_ip/b_p≥1/h · b_p.

    Thus, X = z'_ip / (4h · b_p), 
    x = (z_ip + 1)/(4h · b_p), = 1 / (2h · b_p), 
    and α satisfy the conditions 
    of <ref>. (In particular, ≤α≤ 1.) 
    This claim now yields
    
    [exp*z'_ip/4h · b_p] 
                ≤exp*z_ip+1/4h · b_p - 1/2·1/2h · b_p
                = exp*z_ip/4h · b_p.





    Potential Monotonicity.




    For each node i, it holds that [Φ'_i] ≤Φ_i.



    First, assume that i ∉ S, where S is the considered hyperedge. By
    <ref>, z'_ik = z_ik for every integer k ≥ 1.
    In such case, Φ'_i = Φ_i (for all outcomes of the random process in
    the considered step), which trivially implies [Φ'_i] = Φ_i.

    Hence, in the following, we assume that i ∈ S.
    For each integer k ≥ 1, we relate z'_ik to z_ik.
    Let p = p(i) be the current phase of node i (before processing hyperedge S).
    By <ref>, 
    
    z'_ik = z_ik      for every k ≠ p.

    Note that (<ref>) holds not only in expectation, but for all 
    realizations of the random variable z'_ik.
    Using the definition of Φ'_i and applying
    (<ref>) yields
    
    Φ'_i 
                = exp*z'_ip/4h · b_p 
                + ∑_k ≠ pz'_ik/4h · b_k 
            = exp*z'_ip/4h · b_p 
                + ∑_k ≠ pz_ik/4h · b_k
        = exp*z'_ip/4h · b_p·exp*∑_k ≠ pz_ik/4h · b_k



In the last line above, the former multiplier is a random variable, while the
latter one is a deterministic value. We can now apply expectation to both sides,
which gives us

    [Φ'_i]
            = [s]*exp*z'_ip/4h · b_p·exp*∑_k ≠ pz_ik/4h · b_k
       ≤exp*z_ip/4h · b_p·exp*∑_k ≠ pz_ik/4h · b_k      (by <ref>)
        = Φ_i.        (by the definition of Φ_i)






At any time, Φ≤ n. 



The proof follows inductively. At the beginning, Φ = n by
<ref>. By <ref>, if we
randomly choose the color for a new hyperedge (using the random process
described in this section), it is guaranteed that the potential does not
increase in expectation. Thus, there exists a deterministic choice of the color
for the new hyperedge that does not increase the potential.





At any time, and for each node i, Φ_i ≤ n. 



By <ref>, Φ = ∑_i ∈ [n]Φ_i ≤ n. 
The claim follows because all Φ_i are positive.









§ UPPER-BOUNDING THE DEGREES




 §.§ Estimating Variables w (Proof of <ref>)



So far, we have shown that the potential is always at most n. This allows us to control the
weighted average of z_ik. Recall that z_ik = w_ik - 2 · d(c_ik). 
Thus, to estimate variables w_ik, we first need to upper-bound d(c_ik).

We start with the following technical claim (proven in <ref>). 
H_m denotes the m-th harmonic number.

claimharmonic

    For each k ≥ 1 it holds that H_b_k - H_b_k-t_k≤ln (4 · n).




    Fix a node i and an integer k ≥ 1.
    Then, w_ik≤  z_ik + 2 h · b_k ·ln(4· n).



    Note that at all times, c_ik≤ t_k. 
    Using the definition of z_ik 
    and the monotonicity of the function d_k, we get
    
    w_ik  
            = z_ik + 2 · d_k(c_ik) 
            ≤ z_ik + 2 · d_k(t_k).

    It remains to upper-bound d_k(t_k). Using the definition of d_k,
    
    d_k(t_k) 
                = ∑_j=1^t_k1/α_k(j)
            = ∑_j=1^t_kh · b_k/b_k - j + 1
            = ∑_j=b_k-t_k+1^b_kh · b_k/j
        = h · b_k · (H_b_k - H_b_k-t_k) 
            ≤ h · b_k ·ln(4 · n).
                      (by <ref>)

    The lemma follows by plugging the bound on d_k(t_k) above 
    into (<ref>).



Finally, we can prove the main result of this section, restated below for convenience.

*


It is sufficient to show the lemma right after the last increase of
∑_k=1^ℓ w_ik. All values of the variables in the proof below are
taken at this point. By <ref>, Φ_i ≤ n. Using
the definition of Φ_i we get

    ∑_k ≥ 1z_ik/4 h · b_k = lnΦ_i ≤ln n.

Note that for every k > ℓ, we have w_ik = c_ik = 0,
and thus also z_ik = 0. 
That is, 

    ln n 
        ≥∑_k ≥ 1z_ik/4 h · b_k
        = ∑_k=1^ℓz_ik/4 h · b_k≥1/4h · b_ℓ·∑_k=1^ℓ z_ik.

We can now sum the guarantee of <ref> over all phases from 1 to ℓ and get

    ∑_k=1^ℓ w_ik   ≤∑_k=1^ℓ z_ik + 2 h ·ln(4· n) ·∑_k=1^ℓ b_k 
       ≤ 4 h · b_ℓ·ln n + 4 h ·ln(4· n) · b_ℓ      (by (<ref>) and the definition of b_k)
       ≤ 8 h · b_ℓ·ln(4· n).










 §.§ Estimating Variables w* (Proof of <ref>)



As mentioned in <ref>, we now construct a charging scheme that
maps the increments of variables w^*_iℓ to the increments of other variables
w_ik. This allows us to prove <ref>.


    
    At any time, each node i, and each ℓ≥ 1, 
    we have w^*_iℓ≤∑_j ∈ [n]∑_k=1^ℓ-h w_jk.



    By the definition of , the value of w^*_iℓ is incremented only
    when ℓ = p(i), node i is contained in the considered hyperedge S,
    and ℓ≥ + h. By the definition of , this means that there
    exists at least one node j ∈ S such that p(j) =, and thus the
    value of w_j, is also incremented.

    We can thus map each increment of w^*_iℓ to an increment of
    w_jk for some j and k ≤ℓ-h, and such a mapping is injective.   
    This means that whenever the left hand side of the lemma inequality
    increases by 1, the right hand side increases by at least 1, concluding
    the proof.


*


    Fix any integer ℓ'. Using <ref>, we get
    
    w^*_iℓ'≤∑_j ∈ [n]∑_k=1^ℓ'-h w_jk   ≤ n · 8 h · b_ℓ'-h·ln(4· n) 
                      (by <ref>)
       ≤ 8 h · b_ℓ'·ln(4· n).
                      (as b_k = 2^k and h = log n)

    Hence, ∑_k=1^ℓ w^*_ik≤ 16 h · b_ℓ·ln(4· n). 








§ CONCLUSIONS


In this paper, we have constructed a deterministic O(log^2 n)-competitive
algorithm for the DSC problem. Closing the remaining logarithmic gap between the
current upper and lower bounds is an interesting open problem, which seems to
require a new algorithm that goes beyond the phase-based approach of our and
previous work.

We developed new derandomization techniques that extend the existing potential
function methods. In particular, we tackled the combination of concentration
bound and coupon collector's arguments used in the solution of Emek et
al. <cit.>. We hope that these extensions will be useful for
derandomizing other randomized online algorithms, and eventually for providing a
coherent online derandomization toolbox.

















§ PROOFS OF TECHNICAL CLAIMS



*


Using α≥, we obtain

    (1+/α) · (1 - /(2α)) = 1 + /(2α) - ^2/(2α^2) ≥ 1.

Next, we use the relation ^-y≤ (1+y)^-1 (holding for every y > -1) 
and (<ref>) to argue that

    exp(-  / α) 
        ≤ (1+/α)^-1≤ 1-/(2α).

Finally, this gives

    [^X] 
            = α·exp(x-/α) + (1-α) ·exp(x) 
        = ^x·(α·exp(-/α) + 1-α) 
       ≤^x·(α - /2 + 1-α)       (by (<ref>))
       ≤^x-/2.       (as 1-/2 ≤^-/2 for each )




*


    First, we note that ln m ≤ H_m ≤ 1 + ln m = ln (· m)
    for every m ≥ 1. Thus, 
    
    H_b_k - H_b_k-t_k≤ln(· b_k) - ln(b_k - t_k).

    If b_k < 4n, the claim follows immediately. 
    Otherwise, 
    
    b_k-t_k
                = b_k - ⌈1-1/(2n)· b_k ⌉      (by the definition of t_k)
       ≥ b_k - (1-1/(2n) ) · b_k - 1 
        = b_k/(2n) - 1 
       ≥ b_k / (4n).
                      (as b_k ≥ 4n)
  
    Plugging this bound to (<ref>) yields H_b_k - H_b_k-t_k≤ln(· b_k) - ln(b_k / (4n)) = ln(4 · n). 
    


