  We show that the popular water-filling algorithm for maximizing the mutual
information in parallel Gaussian channels is sub-modular. The sub-modularity of
water-filling algorithm is then used to derive online basestation allocation
algorithms, where mobile users are assigned to one of many possible
basestations immediately and irrevocably upon arrival without knowing the
future user information. The goal of the allocation is to maximize the sum-rate
of the system under power allocation at each basestation. We present online
algorithms with competitive ratio of at most 2 when compared to offline
algorithms that have knowledge of all future user arrivals.
