On the complexity of SINR outage constrained max-min-fairness multicell coordinated beamforming problem

Max-min-fairness (MMF), which concerns optimizing the worst signal-to-interference-plus-noise ratio (SINR) performance of receivers, is a popular transmitter design criterion in multiuser communications. In the single-input single-output (SISO), multiple-input single-output (MISO), and single-input multiple-output (SIMO) interference channels with perfect channel state information at the transmitters, it has been shown that the MMF power allocation and beamforming design problems are polynomial-time solvable, and efficient optimization algorithms exist. In this paper, we assume that the transmitters have channel distribution information only, and study the MMF coordinated beamforming design problem under probabilistic SINR outage constraints. While such a problem is non-convex, it was not clear if it is polynomial-time solvable. We propose a complexity analysis, showing that the SINR outage constrained MMF problem is polynomial-time solvable in the SISO scenario whereas it is NP-hard in the MISO scenario. The NP-hardness is established by showing that the MISO MMF problem is at least as difficult as the 3-satisfiability problem which is NP-complete.