Can this randomized greedy algorithm be made online? Or being proved impossible?

Question

I am going to edge color an undirected simple graph. The following randomized offline algorithm is showed at Online Algorithms for Edge Coloring.

Offline: The potential colors are ordered 1, 2, . . . , 2$\Delta$−1. The edges are ordered at random, and we greedily assign color 1 until a maximal matching is colored 1, then we start over with a random order of the remaining uncolored edges and we greedily assign color 2 until a maximal matching of the remaining edges is colored 2, and so on with the remaining edges and maximal matchings for colors 3, 4, . . .

In paper Online Algorithms for Edge Coloring, the authors claimed the offline algorithm is the same as the online algorithm as follows.

Online: The edges are ordered at random only once, and each edge in turn is colored with the least valid color out of 1, 2, . . . , 2$\Delta$ − 1.

The "same" means, for a given graph. If the first algorithm needs $c$ colors with probability $p$, then the second algorithm uses needs $c$ colors with probability $p$. So there is not clear justification that the given two algorithms are same.

The paper claims "For the second algorithm, if we consider sequentially when colors 1, 2, . . . are assigned, the same bound holds.".

In fact, they turn out to be different (see the examle below). So my question is: can the offline algorithm be made onlne? I cannot handle the multi-times random ordering ( after each maximal matching is removed, the order of the remaining edges is shuffled).

Example. Let $E_r=\{e_0, e_1, e_2\}$, $X_i$ be the indicator random variable that whether color $i$ is assigned to one edge from $E_r$. $X_i=1$ iff the i-th color is not assigned to the edges e_0, e_1, e_2. We calulate the expected number of colors from clolrs $\{1, 2\}$ which are not assinged to any of $\{e_0, e_1, e_2\}$.

For the "first algorithm": $E[X_1+X_2] = Pr(X_1=1)+Pr(X_2=1) $ $=Pr(X_1=1)+Pr(X_2=1|X_1=1)\cdot Pr(X_1=1) + Pr(X_2=1|X_1=0)\cdot Pr(X_1=0)$ $=(\frac{2}{3})^3 + (\frac{1}{2})^3 \cdot (\frac{2}{3})^3 + (\frac{1}{2})^2 \cdot (1- (\frac{2}{3})^3 )$ $=\frac{1}{2}$

For the "second algorithm": We list all the $9!$ orderings, and get $E[X_1+X_2]=12/27=0.44444$.

The follwoing is responce for @vzn, thanks very much.

1. In fact, the paper was not published as far as I know. I have contacted the first author, he have not respond it in detail. The key is that, it does not "fit" clearly.
2. Why I only concern the first two colors in the example. If $x$ edges from $\{e_0, e_1, e_2\}$ are not assigned to colors in $\{1,2\}$, then the algorithms needs exactly $2+(3-x)=5-x$ colors. Because for the remaining $(3-x)$ edges incident to the root not colored, $(3-x)$ new colors have to be used. While the other edges will be colored in the third color definitely. Put another way, if the two algorithms were the same, all the characterizations of them should be the same? (For example, $E[X_1+X_2]$ here. Am I right? I am not sure.)

Answer 1

as far as I can tell after looking into this somewhat, there is a misunderstanding of the paper in the question. the question states that some of the algorithms are offline vs some online. but the algorithms in the paper are all online it appears (but agree the authors are not clear on this point). that is what is accomplished by having random edge orderings-- the random edge ordering reflects edges coming "online" in whatever order, right?

the authors seem to make no reference to "offline" algorithms in the paper and they refer to "online" only in the introduction that I see. they dont state this but the 1st algorithm seems to allow edges to come "online" in "batches" (ie random reordering in stages) whereas the 2nd algorithm does not.

while you dont state it exactly you appear to be checking the math in proof for theorem 2.3 in the paper (p3) which establishes a lower bound on the number of colors in a tree and the authors assert it works for both algorithm 1 and 2 ("for the 2nd algorithm.. the same bound holds"). the proof is that no less than $1.23\Delta$ colors ($\Delta$=graph degree) are sufficient for all trees. it seems if this theorem is wrong as you are suggesting then one should be able to exhibit a tree that can be colored with fewer than $1.23\Delta$ colors using those algorithms. from what I can tell your math is off because you are not expressing it using the same formulas in the proof eg you do not calculate the exponential formula in the proof.

a way to empirically verify this lower bound would be to generate many random trees, or some sample from some distribution, run the two algorithms and verify that they always use at least $1.23\Delta$ colors.