User Association Under SINR Constraints in HetNets: Upper Bound and NP-Hardness

This letter studies the multi-slot user association problem (MSA) under signal-to-interference-plus-noise ratio (SINR) constraints in heterogeneous cellular networks. MSA consists of associating a set of users to a set of base stations during a set of slots while guaranteeing the SINR requirements of the associated users. To solve MSA, we study its single-slot version, called single-slot user association problem (SSA). We provide an upper bound of the optimal solution of MSA using SSA and prove its tightness. Next, we simplify the NP-hardness proof and show that both the SSA and MSA are NP-hard using a new and simple polynomial-time reduction. Finally, we present the simulation results to illustrate the tightness of the upper bound.