  The coded caching scheme proposed by Maddah-Ali and Niesen (MAN) transmits
coded multicast messages to users equipped with caches and it is known to be
optimal within a constant factor. This work extends this caching scheme to
two-hop relay networks with one main server with access to a library of $N$
files, and $H$ relays communicating with $K$ users with cache, each of which is
connected to a random subset of relays. This topology can be considered as a
generalized version of a celebrated family of networks, referred to as
combination networks. Our approach is simply based on routing MAN packets
through the network. The optimization of the routing can be formulated as a
Linear Program (LP). In addition, to reduce the computation complexity, a
dynamic algorithm is proposed to approach the LP solution. Numerical
simulations show that the proposed scheme outperforms the existing caching
schemes for this class of networks.
