Submodular Optimization with Submodular Cover and Submodular Knapsack\n Constraints

We investigate two new optimization problems -- minimizing a submodular\nfunction subject to a submodular lower bound constraint (submodular cover) and\nmaximizing a submodular function subject to a submodular upper bound constraint\n(submodular knapsack). We are motivated by a number of real-world applications\nin machine learning including sensor placement and data subset selection, which\nrequire maximizing a certain submodular function (like coverage or diversity)\nwhile simultaneously minimizing another (like cooperative cost). These problems\nare often posed as minimizing the difference between submodular functions [14,\n35] which is in the worst case inapproximable. We show, however, that by\nphrasing these problems as constrained optimization, which is more natural for\nmany applications, we achieve a number of bounded approximation guarantees. We\nalso show that both these problems are closely related and an approximation\nalgorithm solving one can be used to obtain an approximation guarantee for the\nother. We provide hardness results for both problems thus showing that our\napproximation factors are tight up to log-factors. Finally, we empirically\ndemonstrate the performance and good scalability properties of our algorithms.\n