An Algorithm for the K Best Solutions of the Resource Allocation Problem

An algorithm is presented for obtaining the K best solutions of the resource allocauon problem with an objective function which is the sum of convex functions of one variable It requires O(T* + Klog K + Kn~ogn) time and O(Kn~ogn + n) space, where n is the number of variables and T* ~s the computatmnal time to obtain the best solution KEY WORDS AND PHRASES resource aUocatmn problem, K best soluuons, computational complexity CR CATEGORIES 5 25, 5 30, 5 41 O(Nlogn + n). The method of [27] requires O(c(n, N) + nlogn) time, where c(n, N)