Globally Optimal Joint Uplink Base Station Association and Beamforming

Wei Liu, Ruoyu Sun, Zhi Quan Luo

Research output: Contribution to journalArticlepeer-review


In this paper, we consider the joint base station (BS) association, power control, and beamforming problem for an uplink SISO/SIMO cellular network under the max-min fairness criterion. We first prove a strange discrepancy: a normalized fixed point (NFP) iterative algorithm has geometric convergence to global optima, but it only has pseudo-polynomial time complexity and thus whether the problem is NP-hard or not is an open question. In this paper, we resolve this discrepancy by proving that this problem is indeed polynomial-time solvable. Our proof is based on converting this mixed integer programming (MIP) problem to a series of auxiliary convex problems. Our results fill in a gap in the understanding of the computational complexity of BS association problem. Another implication of our result is that the uplink SIMO problem is easy, but either changing uplink to downlink or changing SIMO to MIMO will make the problem NP-hard. Empirically, the polynomial time algorithm converges much slower than the NFP algorithm, leaving open the question of whether a polynomial time algorithm that converges fast in practice exists for this problem.

Original languageEnglish (US)
Article number8704913
Pages (from-to)6456-6467
Number of pages12
JournalIEEE Transactions on Communications
Issue number9
StatePublished - Sep 2019


  • Base station association
  • beamforming
  • max-min
  • power control
  • uplink

ASJC Scopus subject areas

  • Electrical and Electronic Engineering


Dive into the research topics of 'Globally Optimal Joint Uplink Base Station Association and Beamforming'. Together they form a unique fingerprint.

Cite this