<p>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 <em>all</em> 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? </p>

<p>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.</p>

<p>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 <em>using those algorithms</em>. 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.</p>

<p>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.</p>

CC BY-SA 3.0
2012-02-08T18:01:14.013Z
First, thank you very much for your detailed response. The words you referenced "online in batch" is not really online in my sense. I consider the edges comes online in a random order (yes, one-pass. if the edges comes in batch, you requires the edges comes many passes. Not Online Anymore.). In this way, the first algorirthm (which I called "offline" is different with the second algorith ( which I called "online"). The theorem 2.3 is not complete in someway if you look carefully into the recurrence relation. But I have completed it. (I will add the remainning comment in the next comment. )
Peng Zhang
CC BY-SA 3.0
2012-02-08T18:06:00.280Z
:Besides, the theorem 2.3 correctly analyses the first algoirthm, how can the analysis directedly hold for the second algorithm? That's what I am really interested. At last, empirical verification is not my point rightnow.
Peng Zhang
CC BY-SA 3.0
2012-02-09T12:41:33.733Z
The lower bound may be correct even if the proof is not.
Jeffε
CC BY-SA 3.0
2012-02-13T13:20:37.550Z
@JɛﬀE: You are definitely right. What I am doing is proving the lower bound or disproving it. The paper made an assertion without justification. That's what aroused my interest. Thank you very much.
Peng Zhang
CC BY-SA 3.0
2012-02-08T17:02:59.233Z
2012-02-08T17:11:45.273Z
2012-02-08T17:11:45.273Z
vzn
<p>I am going to <a href="http://en.wikipedia.org/wiki/Edge_coloring" rel="nofollow noreferrer">edge color</a> an undirected simple graph. The following randomized offline algorithm is showed at <a href="http://theory.stanford.edu/~tomas/col.ps" rel="nofollow noreferrer">Online Algorithms for Edge Coloring</a>. </p>

<p><strong>Offline</strong>: 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, . . .</p>

<p>In paper <a href="http://theory.stanford.edu/~tomas/col.ps" rel="nofollow noreferrer">Online Algorithms for Edge Coloring</a>, the authors claimed the offline algorithm is the same as the online algorithm as follows. </p>

<p><strong>Online</strong>: 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.</p>

<p>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.</p>

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

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

<p><strong>Example</strong>.
<img src="https://i.sstatic.net/NnE6U.jpg" alt="Figure">
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 <strong>not</strong> 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\}$.</p>

<p>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}$</p>

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

<p>The follwoing is responce for @vzn, thanks very much.</p>

<ol>
<li>In fact, <strong>the paper was not published as far as I know</strong>. I have contacted the first author, he have not respond it in detail. The key is that, it does not "fit" clearly. </li>
<li><strong>Why I only concern the first two colors in the example.</strong> 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.)</li>
</ol>

CC BY-SA 3.0
2012-02-06T19:34:09.210Z
Why do they turn out to be different? is randomisation over colors has been tried?
singhsumit
CC BY-SA 3.0
2012-02-06T23:39:32.087Z
Please clarify what you mean by "same" and "different." The paper you link does not say "same" anywhere, as far as I see.
Yoshio Okamoto
CC BY-SA 3.0
2012-02-07T07:17:28.250Z
@singhsumit: I have just updated the questio. The intuition of different is that, the first algorithm needs randomness many times, while the second algorithm only needs one randomness. Thank you for your comment.
Peng Zhang
CC BY-SA 3.0
2012-02-07T07:20:51.553Z
@YoshioOkamoto: I have updated the question. Let's consider a given order of the $m$ edges, for the second algorithm, the probability of that order occurs is clear $1/(n!)$. While for the first algorithm, this is not clear. The paper analysed the first algorithm, then uses the analysis directly to the second one.  I have given an example in the question. Thank you very much.
Peng Zhang
CC BY-SA 3.0
2012-02-07T10:45:58.123Z
How did you compute the expectations?  Is this your smallest counterexample?
Jeffε
CC BY-SA 3.0
2012-02-07T10:53:48.100Z
You refer to "paper 2" with a link to a Wikipedia article.  Was that your intention?
András Salamon
CC BY-SA 3.0
2012-02-07T13:52:17.237Z
@JɛﬀE:For the first algorithm, I use law of total probability. For the second algorithm, I consider all the possible orderings. I have added this to the question. I do not whether it is the smallest example or not. Thank you very much. :-)
Peng Zhang
CC BY-SA 3.0
2012-02-07T13:53:26.907Z
@András Salamon: I am sorry. I hard-coded the link number in the text. I have fixed it. Thank you so much. :-)
Peng Zhang
CC BY-SA 3.0
2012-02-07T19:41:31.633Z
havent studied this closely yet but it appears if what you are saying is correct, the authors have made an error in their paper such that one of their propositions (given without proof) does not apply, and that you have found a counterexample. have you tried contacting them?
vzn
CC BY-SA 3.0
2012-02-07T20:03:55.420Z
reading the paper the authors seem to be implying (but not stating exactly) that _all_ their algorithms in the paper are online algorithms... right? they refer to "online" only in the introduction & not elsewhere it seems & dont see term "offline" used anywhere in paper. also I do see proofs of their assertions. so if there is a counterexample then there would be some reason it doesnt "fit" in the proofs.
vzn
CC BY-SA 3.0
2012-02-07T20:19:05.427Z
for your example isnt delta=3 therefore 2*delta-1 = 5? but you seem to be coloring your example only with 2 colors?
vzn
CC BY-SA 3.0
2012-02-08T02:02:12.700Z
@vzn: 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. For your second question, 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. That's why I only concerns the first two colors.
Peng Zhang
CC BY-SA 3.0
2012-02-08T02:28:12.043Z
its great you're checking all the math behind the assumptions/theory, but doesnt the algorithm color your example? are you saying your example is not colorable by the algorithm?
vzn
CC BY-SA 3.0
2012-02-08T04:15:23.603Z
@vzn: A graph can be colored at least $\Delta$ and at most $\Delta+1$ colors offline deterministically. The two algorithms I referenced in the question actually made decision greedily the same way, so they both can color a graph within at most $2\Delta-1$ colors. I am not very clear about "not colorable" in your comment. Thank you very much. :-)
Peng Zhang
CC BY-SA 3.0
2012-02-08T16:42:38.103Z
I feel I'm stupid, but would you explain how you get $\Pr(X_1=1)=(2/3)^3$ more in detail? However, my naive simulation tells for the first algorithm the expectation of X1+X2 is approximately 1.490 and for the second algorithm the expectation is approximately 1.555. I feel I misunderstand something.
Yoshio Okamoto
CC BY-SA 3.0
2012-02-08T18:15:34.167Z
@YoshioOkamoto: I am sorry I may not state exactly what I meant to. Let $E_r=\{e_0,e_1,e_2\}$ and the colors are numbered from $col_1, col_2, \cdots $. Let $X_i=1$ iff $col_i$ is**not** assigned to one of $E_r$. Let $E_i$ be the event that $e_i$ is colored by $col_1$. So $\overline E_0 \bigcap \overline E_1 \bigcap \overline E_2$ happens iff $ ( (E_3 \bigcup E_4) \bigcap (E_5 \bigcup E_6) \bigcap (E_7 \bigcup E_8) )$. Note that $\overline E_3 \bigcap \overline E_4$ happens iff $E_0$ comes before $E_3$ and $E_4$ in the ordering. Therefore, $Pr(X_1=1)=(1-\frac{1}{3})^3$. Thank you so much.
Peng Zhang
CC BY-SA 3.0
2012-02-08T18:20:01.463Z
@Yoshio Okamoto: Consider the root only has two children. The $(\frac{2}{3})^2$ can also be built from law of total probabiliy, conditioned on whether $e_0$ comes before $e_1$ or not. Then we can prove the general number of root's children inductively. Actually I did this to convince myself, while my friend told me the way of "if and only if relation between events". That's pretty cool.
Peng Zhang
CC BY-SA 3.0
2012-02-08T18:21:49.540Z
@Yoshio Okamoto: the answer by vzn does not answer my problem. I want to know whether the first algorithm which needs randomness many times(rounds) be made really online (random only one time).
Peng Zhang
CC BY-SA 3.0
2012-02-09T00:15:10.260Z
Thanks. Please update the description in your question so that X_i=1 if the i-th color is *not* assigned to the edges e_0, e_1, e_2. Then, my naive simulation tells the expectation is approximately 0.510 for the first algorithm, and approximately 0.444 for the second algorithm.
Yoshio Okamoto
CC BY-SA 3.0
2012-02-09T03:50:01.650Z
@YoshioOkamoto: Thank you for your notice.
Peng Zhang
<ds.algorithms><randomized-algorithms>
Can this randomized greedy algorithm be made online? Or being proved impossible?
Peng Zhang
# Can this randomized greedy algorithm be made online? Or being proved impossible?

(Asked by: username_0 on 2012-02-06)

I am going to [edge color](http://en.wikipedia.org/wiki/Edge_coloring) an undirected simple graph. The following randomized offline algorithm is showed at [Online Algorithms for Edge Coloring](http://theory.stanford.edu/~tomas/col.ps).

**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](http://theory.stanford.edu/~tomas/col.ps), 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**.
![Figure](https://i.sstatic.net/NnE6U.jpg)
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.)

**Tags:** ds.algorithms, randomized-algorithms
> **Comments:**
> **username_1**: Why do they turn out to be different? is randomisation over colors has been tried?  
> **username_2**: Please clarify what you mean by "same" and "different." The paper you link does not say "same" anywhere, as far as I see.  
> **username_0**: @singhsumit: I have just updated the questio. The intuition of different is that, the first algorithm needs randomness many times, while the second algorithm only needs one randomness. Thank you for your comment.  
> **username_0**: @YoshioOkamoto: I have updated the question. Let's consider a given order of the $m$ edges, for the second algorithm, the probability of that order occurs is clear $1/(n!)$. While for the first algorithm, this is not clear. The paper analysed the first algorithm, then uses the analysis directly to the second one.  I have given an example in the question. Thank you very much.  
> **username_3**: How did you compute the expectations?  Is this your smallest counterexample?  
> **username_4**: You refer to "paper 2" with a link to a Wikipedia article.  Was that your intention?  
> **username_0**: @JɛﬀE:For the first algorithm, I use law of total probability. For the second algorithm, I consider all the possible orderings. I have added this to the question. I do not whether it is the smallest example or not. Thank you very much. :-)  
> **username_0**: @András Salamon: I am sorry. I hard-coded the link number in the text. I have fixed it. Thank you so much. :-)  
> **username_5**: havent studied this closely yet but it appears if what you are saying is correct, the authors have made an error in their paper such that one of their propositions (given without proof) does not apply, and that you have found a counterexample. have you tried contacting them?  
> **username_5**: reading the paper the authors seem to be implying (but not stating exactly) that _all_ their algorithms in the paper are online algorithms... right? they refer to "online" only in the introduction & not elsewhere it seems & dont see term "offline" used anywhere in paper. also I do see proofs of their assertions. so if there is a counterexample then there would be some reason it doesnt "fit" in the proofs.  
> **username_5**: for your example isnt delta=3 therefore 2*delta-1 = 5? but you seem to be coloring your example only with 2 colors?  
> **username_0**: @vzn: 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. For your second question, 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. That's why I only concerns the first two colors.  
> **username_5**: its great you're checking all the math behind the assumptions/theory, but doesnt the algorithm color your example? are you saying your example is not colorable by the algorithm?  
> **username_0**: @vzn: A graph can be colored at least $\Delta$ and at most $\Delta+1$ colors offline deterministically. The two algorithms I referenced in the question actually made decision greedily the same way, so they both can color a graph within at most $2\Delta-1$ colors. I am not very clear about "not colorable" in your comment. Thank you very much. :-)  
> **username_2**: I feel I'm stupid, but would you explain how you get $\Pr(X_1=1)=(2/3)^3$ more in detail? However, my naive simulation tells for the first algorithm the expectation of X1+X2 is approximately 1.490 and for the second algorithm the expectation is approximately 1.555. I feel I misunderstand something.  
> **username_0**: @YoshioOkamoto: I am sorry I may not state exactly what I meant to. Let $E_r=\{e_0,e_1,e_2\}$ and the colors are numbered from $col_1, col_2, \cdots $. Let $X_i=1$ iff $col_i$ is**not** assigned to one of $E_r$. Let $E_i$ be the event that $e_i$ is colored by $col_1$. So $\overline E_0 \bigcap \overline E_1 \bigcap \overline E_2$ happens iff $ ( (E_3 \bigcup E_4) \bigcap (E_5 \bigcup E_6) \bigcap (E_7 \bigcup E_8) )$. Note that $\overline E_3 \bigcap \overline E_4$ happens iff $E_0$ comes before $E_3$ and $E_4$ in the ordering. Therefore, $Pr(X_1=1)=(1-\frac{1}{3})^3$. Thank you so much.  
> **username_0**: @Yoshio Okamoto: Consider the root only has two children. The $(\frac{2}{3})^2$ can also be built from law of total probabiliy, conditioned on whether $e_0$ comes before $e_1$ or not. Then we can prove the general number of root's children inductively. Actually I did this to convince myself, while my friend told me the way of "if and only if relation between events". That's pretty cool.  
> **username_0**: @Yoshio Okamoto: the answer by vzn does not answer my problem. I want to know whether the first algorithm which needs randomness many times(rounds) be made really online (random only one time).  
> **username_2**: Thanks. Please update the description in your question so that X_i=1 if the i-th color is *not* assigned to the edges e_0, e_1, e_2. Then, my naive simulation tells the expectation is approximately 0.510 for the first algorithm, and approximately 0.444 for the second algorithm.  
> **username_0**: @YoshioOkamoto: Thank you for your notice.  

---

## 1 answers

### Answer by username_5 on 2012-02-08. Score: -3

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.

> **Comments:**
> **username_0**: First, thank you very much for your detailed response. The words you referenced "online in batch" is not really online in my sense. I consider the edges comes online in a random order (yes, one-pass. if the edges comes in batch, you requires the edges comes many passes. Not Online Anymore.). In this way, the first algorirthm (which I called "offline" is different with the second algorith ( which I called "online"). The theorem 2.3 is not complete in someway if you look carefully into the recurrence relation. But I have completed it. (I will add the remainning comment in the next comment. )  
> **username_0**: :Besides, the theorem 2.3 correctly analyses the first algoirthm, how can the analysis directedly hold for the second algorithm? That's what I am really interested. At last, empirical verification is not my point rightnow.  
> **username_3**: The lower bound may be correct even if the proof is not.  
> **username_0**: @JɛﬀE: You are definitely right. What I am doing is proving the lower bound or disproving it. The paper made an assertion without justification. That's what aroused my interest. Thank you very much.  

---

