An Efficient Framework for Balancing Submodularity and Cost

Abstract

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 ƒ 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 ƒ is a monotone and non-negative submodular function. In these cases, the corresponding computational problem can be solved using a simple greedy (1-1/e)-approximation algorithm.