Changelog Notes - Optimization and Uncertainty
June 16:
- Section 6.2, Example 9: Every week the lottery terminates with probability 1-γ.
May 20:
- Section 5.1.1, Proof of Lemma 18: Choice of i and i' in notation is more consistent now (imho).
- Section 5.1.2, Proof of Theorem 26: The final expression proving the approximation ratio of 4 follows in a very similar way as the one in Section 4.1 for Algorithm 8/9 by applying Bayes formula twice.
May 12:
- Section 4.1: Full independence of the events (reaching box i), (opening box i) and (choosing box i) is not required in the analysis of Algorithm 8/9. The expression Pr[Yi,v = 1] = y*i,v/4 Pr[reach box i] is now obtained by applying Bayes formula twice (and using independence of the realized value vi in box i).
May 5:
- Section 3.3: Lower bound for OnlineMax. Round 1 in the power-of-2-instances is deterministic, subsequently the alive-process starts. Expected value of deterministic algorithms is 2, expected value of offline optimum is n+1. Final result remains the same. Corrected typos.
April 15:
- Updated discussion below Theorem 9 about sample length.
- Proof of Lemma 3: Replaced in the final formula fraction t/n by the correct fraction with the binomial coefficient.
April 14:
- Proof of Lemma 1: Replaced in the final formula fraction t/n by the correct fraction with the binomial coefficient.