We consider the classical problem of approximating the FDMA capacity, where the problem is to allocate disjoint resources (frequencies) to multiple users so as to maximize the sum-utility (data rate). Many heuristic approaches, such as convex relaxation etc,. are known to solve for the FDMA capacity, however, fail to give any theoretical guarantees. We approach this problem via results on greedy algorithms for sub-modular functions. The main result is to show that the capacity of parallel Gaussian channels is a sub-modular function. Following this result, we get a $2$-approximation (which is at least 1/2 times equal) to the optimal FDMA capacity.
Rahul Vaze his Ph.D. from The University of Texas at Austin in 2009. Since Oct. 2009 he is a Reader at the School of Technology and Computer Science, Tata Institute of Fundamental Research, Mumbai, India. His research interest are in multiple antenna communication, ad hoc networks, combinatorial resource allocation. He is a co-recipient of the Eurasip best paper award for year 2010 for the Journal of Wireless Communication and Networking, and recipient of Indian National Science Academy's young scientist award for the year 2013 and Indian National Academy of Engineering's young engineer award for the year 2013.