Niv Buchbinder, Moran Feldman, Seffi Naor, and Roy Schwartz were awarded the SIAM Outstanding Paper Prize at the 2017 SIAM Annual Meeting. They were recognized for their paper, “A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization,” SIAM Journal on Computing, Volume 44, Issue 5 (2015).
The SIAM Outstanding Paper Prizes are awarded annually to the authors of the three most outstanding papers, in the opinion of the selection committee, published in SIAM journals in the three calendar years preceding the year before the award year. Priority is given to papers that bring a fresh look at an existing field or that open up new areas of applied mathematics.
Niv Buchbinder is a faculty member in the Department of Statistics and Operations Research at Tel Aviv University. He received his PhD in computer science from the Technion-Israel Institute of Technology in 2008. From 2008 until 2010 he was a postdoctoral researcher at Microsoft Research, New England at Cambridge, MA. From 2010 until 2012 he was a faculty member at the Open University of Israel. His main research interests are algorithms for combinatorial optimization problems in offline and online settings.
Moran Feldman is currently a faculty member in the Department of Mathematics and Computer Science at the Open University of Israel. He received his PhD from the Technion and was a postdoctoral fellow at École polytechnique fédérale de Lausanne (EPFL). His research focuses on finding approximate solutions for combinatorial problems which cannot be solved exactly either due to their computational difficulty or due to their online nature.
Joseph (Seffi) Naor is currently a professor of computer science at the Technion, where he has been on the faculty since 1991. Prior to that, he was a postdoctoral fellow at the University of Southern California and Stanford University. He is a frequent visiting scientist at Microsoft Research. During 1998-2000 he was a member of the technical staff at Bell Laboratories, Lucent Technologies. Naor’s research interests are mainly in the design and analysis of efficient algorithms, in particular, approximation algorithms for NP-Hard algorithms and online algorithms, algorithmic game theory, and complexity theory. He is currently on the editorial board of
Algorithmica and
ACM Transactions on Algorithms.
Roy Schwartz is a faculty member in the Department of Computer Science at the Technion. He received his PhD from the Technion and was a postdoctoral researcher at the Theory Group and Microsoft Research and the Department of Computer Science at Princeton University. His research focuses on the design and analysis of algorithms, approximation algorithms, combinatorial optimization, the geometry of metric spaces and its applications, submodular optimization, and randomized algorithms.
Q: Why are you excited about winning the prize?
A: In the paper we present new algorithms for several problems in the area of submodular maximization. We are particularly excited about the main new algorithm that settles a fundamental open problem in this area, thus providing a tight guarantee on the performance. The algorithm also uses a very simple and elegant method which turns out to be very efficient and easy to implement in practice. We hope that winning this award will be helpful in drawing attention to our new methods in the broader community of applied mathematics. Such an exposure would be very exciting since it is likely to lead to further applications.
Q: Could you tell us a bit about the research that won you the prize?
A: This research is part of a larger effort of developing better algorithms for optimizing an important class of functions known as submodular functions. Such functions arise in classic settings, e.g., graph theory, matroids, and information theory, as well as in areas that have attracted much attention in recent years, e.g., machine learning, algorithmic game theory, and image processing. Thus, finding better algorithms is likely to lead to better results in these areas. In the research that won the prize we tackle the basic problem of unconstrained submodular maximization and present an algorithm achieving the best possible guarantee. This goal is obtained by introducing a new type of greedy approach that is remarkably fast and simple.
Q: What does your research mean to the public?
A: The optimization problems considered in our research are of a rather abstract nature. Hence, one can view results in this research field as generic tools that can be readily applied to the many practical problems that are (roughly) captured as submodular optimization problems. Just to name a few, these practical problems include movie recommendation systems, video summarization, and detection of splice sites in DNA sequences.
Q: What does being a SIAM member mean to you?
A: The opportunity to attend top conferences and being exposed to cutting edge research.