Fast and Simple Algorithms for Constrained Submodular Maximization

  • 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.

Speaker Details

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 Jeff Running

      Jeff Running

    • Portrait of Roy Schwartz

      Roy Schwartz

Series: Microsoft Research Talks