On an optimization problem with nested constraints (Q583110): Difference between revisions

The problem considered is: maximize \(\sum^{n}_{j=1}f_ j(x_ j)\) subject to \(\sum_{j\in S_ i}x_ i\leq b_ i\), \(i=1,...,m\), \(x_ j\geq 0\) integer. The constraints are assumed to be nested, i.e. with respect to inclusion the graph with vertices \(S_ i\) is a tree. Two algorithms are presented, resp. for the case that each \(f_ j(x_ j)\) is concave, with running time \(O(n \log^ 2n \log \bar b),\) and the case that all \(f_ j\) are equal, with running time \(O(n+m\log m)\). Here \(\bar b\) is less than the largest b.