An Efficient Framework for Balancing Submodularity and Cost
Sofia Maria Nikolakaki, Alina Ene, Evimaria Terzi
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.
Topics & Concepts
Submodular set functionComputer scienceGreedy algorithmMathematical optimizationMonotone polygonMaximizationSimple (philosophy)Function (biology)Recommender systemApproximation algorithmSelection (genetic algorithm)AlgorithmArtificial intelligenceMathematicsMachine learningPhilosophyGeometryBiologyEvolutionary biologyEpistemologyComplexity and Algorithms in GraphsOptimization and Search ProblemsAdvanced Graph Theory Research