||We consider the classical problem of approximating the FDMA capacity,where the problem is to allocate disjoint resources (frequencies) tomultiple users so as to maximize the sum-utility (data rate). Manyheuristic approaches, such as convex relaxation etc,. are known to solvefor the FDMA capacity, however, fail to give any theoretical guarantees.We approach this problem via results on greedy algorithms for sub-modularfunctions. The main result is to show that the capacity of parallelGaussian channels is a sub-modular function. Following this result, we geta 2-approximation (which is at least 1/2 times equal) to the optimalFDMA capacity.
||Rahul Vaze received his Ph.D. from The University of Texas at Austin in 2009. SinceOct. 2009 he is a Reader at the School of Technology and ComputerScience, Tata Institute of Fundamental Research, Mumbai, India. Hisresearch interest are in multiple antenna communication, ad hoc networks,combinatorial resource allocation. He is a co-recipient of the Eurasipbest 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.