Abstract: Allocating disjoint resources to multiple users so as to maximize the sum-utility is a classically hard problem. Finding the FDMA capacity is one such special case, where we have to allocate disjoint frequency bins to multiple users so as to maximize the sum of the data rate. Typically, in wireless applications, heuristic approaches such as convex relaxation, KKT conditions etc,. are used to solve partitioning problem. 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. In addition, exploiting the sub-modularity of the underlying utilities, we also derive a truthful mechanism where no user has any incentive of misreporting its utility and still guarantee a price of anarchy of at most 2.
