Fast and Simple Algorithms for Constrained Submodular Maximization

Опубликовано 22 июня 2016, 1:55

Submodular maximization captures both classical problems in combinatorial optimization and recent more practical applications that arise in other disciplines, e.g., machine learning and data mining. The size of the inputs in these applications is usually very large. Hence, it is interesting to devise approximation algorithms that in addition to providing a provable guarantee are also very fast and simple to use. In this talk I will present one such example and consider the problem of submodular maximization with a cardinality constraint. Additionally, more general constraints will be mentioned with some related open questions.