Asymptotically Optimal Scheduling for Compute-and-Forward.

Consider a Compute and Forward (CF) relay network with $L$ users and a single relay. The relay tries to decode a linear function of the transmitted signals. For such a network, letting all $L$ users transmit simultaneously, especially when $L$, is large causes a significant degradation in the rate the relay is able to decode. In fact, it goes to zero very fast with $L$. Therefore, in each transmission phase only a fixed number of users should transmit, i.e., \emph{users should be scheduled.}

In this work, we provide an asymptotically optimal, polynomial time scheduling algorithm for CF. We show that scheduling under CF not only guarantees non-zero rate, it provides a gain in the system sum-rate, up to the optimal scaling law of $O(\log{\log{L}})$. We do this by first fixing a good, yet sub-optimal, coefficients vector, and devising a polynomial time algorithm to find a sub-set of the users whose channel gains matches the vector. We then prove that this choice is asymptotically optimal.