Revisiting Karp, Vazirani, and Vazirani (STOC 1990): A Simple Yet Rigorous Fix to the $1 - 1/e$ Upper-Bound Analysis

In this paper, we present a comprehensive review of the analysis of the well-known $1 - 1/e$ upper bound on the competitiveness that any online algorithm can achieve, as established in the classical paper by Karp, Vazirani, and Vazirani (STOC 1990). We discuss in detail all the minor and major technical issues in their approach and present a \emph{simple yet rigorous} method to address them. Specifically, we show that the upper bound of $n(1 - 1/e) + o(n)$ on the performance of any online algorithm, as shown in the paper, can be replaced by $\lceil n \cdot (1 - 1/e) + 2 - 1/e \rceil$. Our approach is notable for its simplicity and is significantly less technically involved than existing ones.