Different from the naive greedy algorithm explained in Section 3, the above greedy algorithm is performed on the set of all rooted paths, P. Thus, even if beneficial vertices are far from r, rooted paths that include such beneficial vertices are considered as candidates to be chosen in each iteration.
the constraint that appears in DR-submodular maximization is somewhat easier to deal with than that of our problem; exploiting this, Soma and Yoshida (2017) developed a polynomial-time algorithm that achieves roughly 1 2 -approximation.