Novel combinatorial results on downlink MU-MIMO scheduling with applications

In this paper we consider the classical problem of downlink (DL) multiuser (MU) multi-input-multi-output (MIMO) scheduling with linear transmit precoding. This problem was formulated over a decade ago and has been deeply studied since then. Moreover, MU-MIMO with linear transmit precoding is being increasingly pursued as a key technology by the industry, with a strong emphasis on efficient scheduling algorithms. However, the intractable combinatorial nature of the problem has mostly restricted algorithm design to the realm of simple greedy heuristics. Such algorithms do not exploit any underlying structure in the problem. Recently, it has been formally shown that in general this problem is even hard to approximate. Our significant contribution in this work is to consider the practically most important choices of linear precoding and power allocation and show that the resulting problems can be cast as ones where a difference of two submodular set functions has to be maximized. This opens up a new framework for MU-MIMO scheduler design. We use this framework to design an algorithm and demonstrate that significant gains can be achieved at a reasonable complexity. Our framework can also incorporate analog receive beamforming which is deemed to be essential in mmWave MIMO systems.