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. Our new rounding algorithmsubstantially improves upon the currently best-known complexity for this problem. Moreover , we show the surprising result that under mild Strong-Law-type assumptions on the file request sequence, the rate of file fetches to the caches approaches to zero under the\textsf{LeadCache policy.
After 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 Pipage rounding algorithm. With an additional Strong-Law-type assumption , we show the surprising result that under mild Strong-Law-type assumptions on the file request sequence, the rate of file fetches to the caches approaches to zero under the\textsf{LeadCache policy.