following theorems.

\[th:gconst\] For a caching system with $K$ users, a database of $N$ files, and a local cache size of $M$ files at each user, we have $$\begin{aligned}
            \frac{R_{\textup{u}}(N,K,r)}{2.00884}&\leq  R^*\leq R_{\textup{u}}(N,K,r),\label{eq:ru}\\
            \frac{R_{\textup{u,ave}}(N,K,r)}{2.00884}&\leq  R^*_{\textup{ave}}\leq R_{\textup{u,ave}}(N,K,r).\label{eq:ruave}
            \end{aligned}$$ where $R_{\textup{u}}(N,K,r)$ and $R_{\textup{u,ave}}(N,K,r)$ are defined in Definition \[def\]. Furthermore, if $N$ is sufficiently large (specifically, $N\geq \frac{K(K+1)}{2}$), we have $$\begin{aligned}
            \frac{R_{\textup{u}}(N,K,r)}{2}&\leq  R^*\leq R_{\textup{u}}(N,K,r),\label{eq:lru}\\
            \frac{R_{\textup{u,ave}}(N,K,r)}{2}&\leq  R^*_{\textup{ave}}\leq R_{\textup{u,ave}}(N,K,r).\label{eq:lruave}
            \end{aligned}$$

The above theorem characterizes $R^*$ and $R^*_{\textup{ave}}$ within a constant factor of $2.00884$ for all possible values of parameters $K$, $N$, and $M$. To the best of our knowledge, this gives the best characterization to date. Prior to this work, the best proved constant factors were $4$ for peak rate [@ghasemi15] and $4.7$ for average rate (under uniform file popularity) [@lim2016information]. Furthermore, Theorem \[th:gconst\] characterizes $R^*$ and $R^*_{\textup{ave}}$ for large $N$ within a constant factor of $2$.

The converse bound that we develop for proving Theorem \[th:gconst\] also immediately results in better approximation of rate-memory tradeoff in other scenarios, such as online caching [@pedarsani13], caching with non-uniform demands [@niesen13], and hierarchical caching [@karamchandani14]. For example, in the case of online caching [@pedarsani13], where the current approximation result is within a multiplicative factor of $24$, it can 