  In the classical selection problem, the input consists of a collection of
elements and the goal is to pick a subset of elements from the collection such
that some objective function $f$ is maximized. This problem has been studied
extensively in the data-mining community and it has multiple applications
including influence maximization in social networks, team formation and
recommender systems. A particularly popular formulation that captures the needs
of many such applications is one where the objective function $f$ is a monotone
and non-negative submodular function. In these cases, the corresponding
computational problem can be solved using a simple greedy
$(1-\frac{1}{e})$-approximation algorithm.
  In this paper, we consider a generalization of the above formulation where
the goal is to optimize a function that maximizes the submodular function $f$
minus a linear cost function $c$. This formulation appears as a more natural
one, particularly when one needs to strike a balance between the value of the
objective function and the cost being paid in order to pick the selected
elements. We address variants of this problem both in an offline setting, where
the collection is known a priori, as well as in online settings, where the
elements of the collection arrive in an online fashion. We demonstrate that by
using simple variants of the standard greedy algorithm (used for submodular
optimization) we can design algorithms that have provable approximation
guarantees, are extremely efficient and work very well in practice.
