On an optimization problem with nested constraints (Q583110): Difference between revisions
From MaRDI portal
Changed an Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 08:27, 30 January 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On an optimization problem with nested constraints |
scientific article |
Statements
On an optimization problem with nested constraints (English)
0 references
1990
0 references
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.
0 references
nested constraints
0 references