Content deleted Content added
Line 98:
Let <math>Q = \{0,1\} \cup \{{2\omega_1 \over d}, \ldots,{2\omega_N \over d}\}</math>. Since for each <math>i, \omega_i = \min(\Delta(\mathbf{y_i'}, \mathbf{y_i}), {d \over 2})</math>, we have
where <math>q_1 < \cdots < q_m</math> for some <math>m \le \left \lfloor \frac{d}{2} \right \rfloor</math>. Note that for every <math>\theta \in [q_i, q_{i+1}]</math>, the step 1 of the second version of randomized algorithm outputs the same <math>\mathbf{y}''.</math>. Thus, we need to consider all possible value of <math>\theta \in Q</math>. This gives the deterministic algorithm below.
| |||