as long as $g(A)<g(U)$ repeatedely adds to $A$ an element $u \in U \setminus A$ with maximum $\frac{g(A \cup \{u\})-g(A)}{c_u}$, has approximation ratio $H\left(\max_{u \in U} g(\{u\})-g(\emptyset)\right)$.

We start with the case of edge-costs. Then the function $g$ is defined in the same way as in [@KN-aug]: $U=F$ and for $I \subseteq F$ $$g(I)=\sum_{uv \in D}\min\{r(u,v),f_{uv}(I)\}  .$$ It is not hard to verify that $g$ is non-decreasing, and that $I$ is a feasible solution to an [NA]{} instance if and only if $g(I)=g(F)=r(D)$. Also, $g(\{e\}) - g(\emptyset) \leq \sum_{uv \in D} [f_{uv}(\{e\}) - f_{uv}(\emptyset)]$ for any $e \in F$. We show that $g$ is submodular. It is known (c.f. [@Sch]) that if $h$ is submodular, then $\min\{r,h\}$ is submodular for any constant $r$. Thus the function $h_{uv}(I)=\min\{r(u,v),f_{uv}(I)\}$ is submodular. As a sum of submodular functions is also submodular, we obtain that $g$ is submodular.

Now let us consider node-costs. For $S \subseteq V$ let $F_S$ denote the set of edges in $F$ from $a$ to $S$, and let $f'_{uv}(S)=f_{uv}(F_S)$. We have $U=V$ and for $S \subseteq V$ let $$g'(S)= \sum_{uv \in D}\min\{r(u,v),f'_{uv}(S)\} \ .$$ As in edge-costs case, it is not hard to verify that $g'$ is non-decreasing and that 