Computational Complexity of the Pilot Assignment problem in Cell-Free Massive MIMO

Abstract

Wireless communication is of paramount importance in today’s world, enabling billions of people to connect to each other and the internet, transforming every sector of the economy, and building the foundations for powerful new technologies that hold great promise to improve lives at an unprecedented rate and scale. The rapid increase in the number of devices and the associated demands for higher data rates and broader network coverage fuels the need for more robust wireless technologies. The key technology identified to address this problem is called Cell-Free Massive MIMO (CF-mMIMO). CF-mMIMO is accompanied by many challenges, one of which is efficiently managing limited resources, giving rise to the resource allocation problem in wireless networks. In this thesis, we focus on a major problem that hinders resource allocation in wireless networks, namely the Pilot Assignment problem (PA). While this problem is the focus of active research in engineering, it has received little attention from theoretical computer scientists, despite having several graph-theoretic schemes to tackle it. In the course of this thesis, we delve into the theory of computational complexity and approximability, and establish results pertaining to these concepts for the Pilot Assignment problem with the help of original reductions. We further discuss our findings in the context of the algorithms already proposed in the literature to tackle this problem.