  The joint base station (BS) association and beamforming problem has been
studied extensively in recent years, yet the computational complexity for even
the simplest SISO case has not been fully characterized. In this paper, we
consider the problems for an uplink SISO/SIMO cellular network under the
max-min fairness criterion. We first prove that the problems for both the SISO
and SIMO scenarios are polynomial time solvable. Secondly, we present a fixed
point based binary search (BS-FP) algorithm for both SISO and SIMO scenarios
whereby a QoS (Quality of Service) constrained subproblem is solved at each
step by a fixed point method. Thirdly, we propose a normalized fixed point
(NFP) iterative algorithm to directly solve the original problem and prove its
geometric convergence to global optima. Although it is not known whether the
NFP algorithm is a polynomial time algorithm, empirically it converges to the
global optima orders of magnitude faster than the polynomial time algorithms,
making it suitable for applications in huge-scale networks.
