On the complexity of optimal coordinated downlink beamforming

In a cellular wireless system, users located at cell edges often suffer significant out-of-cell interference. In this paper we consider a coordinated beamforming approach whereby multiple base stations jointly optimize their downlink beamforming vectors in order to simultaneously improve the data rates of a given group of cell edge users. Assuming perfect channel knowledge, we formulate this problem as the maximization of a system utility function (which balances user fairness and average user rates), subject to individual power constraints at each base station. We show that, for the single carrier case and when the number of antennas at each base station is at least two, the optimal coordinated beamforming problem is strongly NP-hard for both the harmonic mean utility function and the proportional fairness utility function. For the min-rate utility function, we show that the problem is solvable in polynomial time.