[link]
The authors introduce two new submodular optimization problems and investigate approximation algorithms for them. The problems are natural generalizations of many previous problems: there is a covering problem ($min\\{ f(X) : g(X) \ge c\\}$) and a packing or knapsack problem ($max\\{ g(X) : f(X) \le b\\}$), where both f and g are submodular. These generalize wellknown previously studied versions of the problems usually assume that f is modular. They show that there is an intimate relationship between the two problems: any polynomialtime bicriterion algorithm for one problem implies one for the other problem (with similar approximation factors) using a simple reduction. They then present a general iterative framework for solving the two problems by replacing either f or g by tight upper or lower bounds (often modular) at each iteration. These tend to reduce the problem at each iteration to a simpler subproblem for which there are existing algorithms with approximation guarantees. In many cases, they are able to translate these into approximation guarantees for the more general problem. Their approximation bounds are curvaturedependent and highlight the importance of this quantity on the difficulty of the problem. The authors also present a hardness result that matches their best approximation guarantees up to log factors, show that a number of existing approximation algorithms (e.g. greedy ones) for the simpler problem variants can be recovered from their framework by using specific modular bounds, and show experimentally that the simpler algorithm variants may perform as well as the ones with better approximation guarantees in practice.
Your comment:
