Optimal joint base station assignment and power allocation in a cellular network

We consider the problem of maximizing the minimum rate by joint BS assignment and power allocation in a cellular network. First, we show that the max-min fairness problem with fixed power vector can be solved in polynomial time. Second, we show that the joint design problem with the constraints that the SINR of each user is at least 0 dB is polynomial time solvable. The key is to transform the subproblem of BS assignment to a maximum weighted matching problem with weights {log(g_ij)}, where g_ij is the channel gain. Third, our transformation motivates a two-stage efficient distributed algorithm for joint BS assignment and power control. Simulation results show that the proposed algorithm outperforms other existing algorithms in terms of the minimum achieved rate.