Fast and Simple Algorithms for Constrained Submodular Maximization


May 29, 2015


Roy Schwartz


Princeton University


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.


Roy Schwartz

Roy Schwartz is currently a postdoctoral research associate at the Department of Computer Science in Princeton University, and formerly he was a postdoctoral researcher at the Theory Group at Microsoft Research. Roy did his Ph.D. under the supervision of Prof. Seffi Naor in the Department of Computer Science at the Technion, which he will be joining the coming academic year. His research focuses on the design and analysis of algorithms and combinatorial optimization, including: approximation algorithms and coping with NP-hardness, the geometry of metric spaces and its applications, submodular optimization, and randomized algorithms.


  • Portrait of Roy Schwartz

    Roy Schwartz