An efficient algorithm for the parametric resource allocation problem (Q1058467)

The parametric resource allocation problem asks to minimize the sum of separable single-variable convex functions containing a parameter \(\lambda\), \(\sum^{n}_{i=1}(f_ i(x_ i)+\lambda g_ i(x_ i))\), under simple constraints \(\sum^{n}_{i=1}x_ i=M\), \(l_ i\leq x_ i\leq u_ i\) and nonnegative integers \(x_ i\) for \(i=1,2,...,n\), where M is a given positive integer, and \(l_ i\) and \(u_ i\) are given lower and upper bounds on \(x_ i\). This paper presents an efficient algorithm for computing the sequence of all optimal solutions when \(\lambda\) is continuously changed from 0 to \(\infty\). The required time is O(G\(\sqrt{M} \log^ 2 n+n \log n+n \log (M/n))\), where \(G=\sum^{n}_{i=1}u_ i-\sum^{n}_{i=1}l_ i\) and an evaluation of \(f_ i(\cdot)\) or \(g_ i(\cdot)\) is assumed to be done in constant time.