Fair Rate Allocation over A Generalized Symmetric Polymatroid with Box Constraints

Abstract

Motivated by the fair rate allocation in a multiaccess Gaussian channel, this paper studies the problem of fair rate allocation over a generalized symmetric polymatroid with box constraints. The best-known algorithm for this problem has time complexity O(n5lnO(1)n). In this paper, we present a divide-and-conquer algorithm for this problem with quadratic running time. It is an implementation of a refined decomposing method for the more general separate concave maximization over a polymatroid with box constraints. A key ingredient of the algorithm is a linear-time algorithm for a generalized knapsack problem.