Before revision:  We show that \textsf{LeadCache is regret optimal up to a multiplicative factor of \tilde{O}(n^{ 0.375 }) . As a byproduct of our analysis, we design a new linear-time deterministic Pipage rounding procedure for the LP relaxation of a well-known NP-hard combinatorial optimization problem in this area.
After revision:  We show that \textsf{LeadCache is regret optimal up to a multiplicative factor of \tilde{O}(n^{ 0.375 }) , where n is the number of users. We implement the policy by designing a new linear-time deterministic Pipage rounding procedure for the LP relaxation of a well-known NP-hard combinatorial optimization problem in this area.