Fast and Simple Algorithms for Constrained Submodular Maximization
308 views · Published 22 June 2016 · 1:00:32 · Indexed 20 September 2026
Channel: Microsoft Research · 2016 · Science & Technology
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.
