of $R^*$ and $R^*_{\textup{ave}}$ as a function of $N$, $K$, and $M$. In this paper, we aim to find converse bounds that characterize $R^*$ and $R^*_{\textup{ave}}$ within a constant factor. Moreover, we aim to better characterize $R^*$ and $R^*_{\textup{ave}}$ for an important case where $N$ ls large, when $K$ and $\frac{M}{N}$ are fixed.

Related Works
-------------

Coded caching was originally proposed in [@maddah-ali12a], where the peak rate vs. memory tradeoff was characterized within a factor of $12$. This result was later extended in [@niesen13], where the minimum average rate under uniform file popularity was characterized within a factor of 72. Since then, various efforts has been made on improving these characterizations [@ghasemi15; @lim2016information; @sengupta15; @DBLP:journals/corr/WangLG16]. The state of the art is an approximation within a factor of $4$ for peak rate [@ghasemi15] and $4.7$ for average rate [@lim2016information].

In this paper, we characterize both the peak rate and the average rate within a factor of $2.00884$, which is about a two-fold improvement upon the prior arts. This improvement is achieved by improving both the achievability scheme and the converse. Specifically, we use the achievability scheme we recently proposed in [@yu2016exact] to upper bound the communication rates. This upper bound strictly 