Two algorithms for maximizing a separable concave function over a polymatroid feasible region (Q1179000)

Let \(E\) be a finite index set, indexing the available projects, of \(\mathbb{R}_ +\) and the set \(\mathbb{R}_ +^ E=\{x(e)_{e\in E}\mid\;x\in\mathbb{R}_ +\}\) of all allocation vectors. If \(S\) is a subset of components of an allocation vector \(x\in R_ +^ E\), the notation \(x(S)=\sum_{e\in S}x(e)\), is adopted. The polymatroid \(F\) is defined by \(F:=\{x\in\mathbb{R}_ +^ E\mid\;x(S)\leq N(S),\;S\subset E\}\), where the function \(N\) on \(2^ E=\{S\mid\;S\subset E\}\) satisfies \(N(\emptyset)=0\); if \(S\subset T\subset E\) then \(N(S)\leq N(T)\); if \(S,T\subset E\) then \(N(S)+N(T)\leq N(S\cup T)+N(S\cap T)\) (\(N\) is called a rank function). In this paper two new algorithms are given for the problem \(P(r,F)\): maximize \(r(x)\) subject to \(x\in F\), where \(r\) is a separable real-valued function on \(\mathbb{R}_ +^ E\), \(r(x)=\sum_{e\in E}r(e,x(e))\) with continuous and concave components \(r(e,.)\). A local characterization of an optimal solution as well as interesting applications are given.