@article{4239697e6d99443780207eed12f06e1f,
title = "Globally Optimal Joint Uplink Base Station Association and Beamforming",
abstract = "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.",
keywords = "Base station association, SISO/SIMO, beamforming, max-min, power control, uplink",
author = "Wei Liu and Ruoyu Sun and Luo, {Zhi Quan}",
note = "Funding Information: The financial support of the National Natural Science Foundation of China (61871452), and of China Scholarship Council (201206965014) are gratefully acknowledged. The work of Z.-Q. Luo is supported by the leading talents of Guangdong province Program (No. 00201501), the National Natural Science Foundation of China (No. 61731018), the Development and Reform Commission of Shenzhen Municipality, and the Shenzhen Fundamental Research Fund (No. KQTD201503311441545). Funding Information: Manuscript received September 20, 2018; revised January 20, 2019 and April 17, 2019; accepted April 24, 2019. Date of publication May 2, 2019; date of current version September 16, 2019. The financial support of the National Natural Science Foundation of China (61871452), and of China Scholarship Council (201206965014) are gratefully acknowledged. The work of Z.-Q. Luo is supported by the leading talents of Guangdong province Program (No. 00201501), the National Natural Science Foundation of China (No. 61731018), the Development and Reform Commission of Shenzhen Municipality, and the Shenzhen Fundamental Research Fund (No. KQTD201503311441545). This paper was presented in part at the International Conference on Acoustics, Speech and Signal Processing (ICASSP), 2014 [1]. The associate editor coordinating the review of this paper and approving it for publication was E. Bj{\"o}rnson. (Corresponding author: Ruoyu Sun.) W. Liu is with the State Key Laboratory of ISN, Xidian University, Xian 710071, China (e-mail: liuweixd@mail.xidian.edu.cn). Publisher Copyright: {\textcopyright} 1972-2012 IEEE.",
year = "2019",
month = sep,
doi = "10.1109/TCOMM.2019.2914448",
language = "English (US)",
volume = "67",
pages = "6456--6467",
journal = "IEEE Transactions on Communications",
issn = "1558-0857",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
number = "9",
}