Budgeted Out-tree Maximization with Submodular Prizes

Gianlorenzo D'Angelo, Esmaeil Delfaraz, Hugo Gilbert

We consider a variant of the prize collecting Steiner tree problem in which we are given a \emph{directed graph} $D=(V,A)$, a monotone submodular prize function $p:2^V \rightarrow…