Submodular Optimization with Submodular Cover and Submodular Knapsack ConstraintsSubmodular Optimization with Submodular Cover and Submodular Knapsack ConstraintsIyer, Rishabh K. and Bilmes, Jeff A.2013
Paper summarynipsreviewsThe 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.
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.