Submodular Optimization with Submodular Cover and Submodular Knapsack Constraints Submodular Optimization with Submodular Cover and Submodular Knapsack Constraints
Paper summary 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 well-known 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 polynomial-time bi-criterion 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 curvature-dependent 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.
papers.nips.cc
scholar.google.com
Submodular Optimization with Submodular Cover and Submodular Knapsack Constraints
Iyer, Rishabh K. and Bilmes, Jeff A.
Neural Information Processing Systems Conference - 2013 via Bibsonomy
Keywords: dblp


Loading...
Your comment:


Short Science allows researchers to publish paper summaries that are voted on and ranked!
About