News & Events > Department News
Bilmes and Iyer Win Best Paper at the 2013 Neural Information Processing Systems Conference
Congratulations to Jeff Bilmes and EE graduate student Rishabh Iyer for receiving the best paper award at the 2013 Neural Information Processing Systems (NIPS) conference. Their paper titled, “Submodular Optimization with Submodular Cover and Submodular Knapsack Constraints” was one of three papers selected at the conference to receive the Outstanding Paper Award. These awards were selected by the committee based on the “quality, originality, and clarity of the submission and its expected future impact.” This is Bilmes and Iyer's second best paper this year; they also received a best paper award at ICML 2013.
Submodular Optimization with Submodular Cover and Submodular Knapsack Constraints
Abstract
We investigate two new optimization problems — minimizing a submodular function subject to a submodular lower bound constraint (submodular cover) and maximizing a submodular function subject to a submodular upper bound constraint (submodular knapsack). We are motivated by a number of real-world applications in machine learning including sensor placement and data subset selection, which require maximizing a certain submodular function (like coverage or diversity) while simultaneously minimizing another (like cooperative cost). These problems are often posed as minimizing the difference between submodular functions [9, 23] which is in the worst case inapproximable. We show, however, that by phrasing these problems as constrained optimization, which is more natural for many applications, we achieve a number of bounded approximation guarantees. We also show that both these problems are closely related and, an approximation algorithm solving one can be used to obtain an approximation guarantee for the other. We provide hardness results for both problems thus showing that our approximation factors are tight up to log-factors. Finally, we empirically demonstrate the performance and good scalability properties of our algorithms.
More Information
Award recipients at NIPS 2013
Jeff Bilmes' faculty page
Rishabh Iyer's web page
