An Algorithm for the K Best Solutions of the Resource Allocation Problem
Naoki Katoh, Toshihide Ibaraki, Hisashi Mine · Journal of the ACM · 1981
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) is the time required to solve the continuous problem P' obtained from P by dropping the integrality condition on the x,.A third type of approach is exemplified by [6, 7,