2014/02/20 by Kiran Koshy Thekumparampil, Thekumparampil, Kiran Koshy, Andrew Thangaraj +3 · 1 citation
Computer Science · Engineering · Mathematics · #Caching and Content Delivery #Data Structures and Algorithms (cs.DS) #Energy Harvesting in Wireless Networks #FOS: Computer and information sciences #Information Theory (cs.IT) #Networking and Internet Architecture (cs.NI) #Optimization and Search Problems #Smart Parking Systems Research #cs.DS #cs.IT #cs.NI #math.IT
paper · pdf · doi:10.48550/arxiv.1402.4892
5 pages, 2 figures; submitted to the International Symposium on Information Theory 2014
arxiv created 2014/02/20 · openalex publication_date 2014/02/20 · arxiv updated 2014/02/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.