Submodular Optimization with Submodular Cover and Submodular Knapsack Constraints
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,25] 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.
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) st. g(X) >= c) and a packing or 
      knapsack problem (max g(X) st. f(X) <= 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. Quality: This is an 
      extremely high quality paper that makes numerous contributions. I 
      especially like the fact that it presents a unifying framework from 
      which many specific results (new and old) can be derived. Thus, it 
      contributes not only to the compendium of approximation results for 
      specific submodular optimization problems, but also to the general way 
      of thinking about the research area. The insights relating 
      approximability to curvature seem to be a separate and interesting 
      thread of contribution. It is a very complete piece of work. 
      Clarity: The paper is also impeccably written. It packs in many 
      results and is thus very dense. But it is well organized and follows a 
      very logical outline that first presents the main ideas and then uses 
      them to instantiate a number of specific results. My one suggestion to 
      the authors is that, for the short version of the paper, perhaps you 
      can consider omitting some of the lesser results to include a bit more 
      discussion. For example, the extensions in Section 4.3 could easily 
      be relegated to the longer version. Two things that would add to the 
      paper are: (1) some interpretation of approximability results and (2) 
      a bit more explanation of the experiments. For example, I had 
      the following question: it seems that the ellipsoidal-based algorithms 
      (e.g. EASSC) give the strongest approximation-guarantees. How should I 
      think about the relationship between the guarantee given by ISSC and 
      EASSC? In practice is the EASSC bound usually better? 
      Originality: while there has been a significant amount of work on 
      submodular optimization, and this paper touches on many specific 
      pieces of prior work, it seems to be quite original in the way it 
      relates all of the prior work within a unifying framework. 
      Significance: I am not an expert in this area, but I think it 
      could be highly significant. One question is how often the most 
      general version of the problem (submodular cost + submodular covering 
      constraint) really crops up in practice vs. the previously studied 
      special cases. Minor comments: * Line 157: "A simple 
      modification of the iterative procedure, however, guarantees 
      improvement". This seems like a counterpoint to some previous point, 
      but I can't figure out which. Perhaps it was orphaned. * Typo in 
      Corollary 4.10: \sqrt{n} \log --> \sqrt{n} \log n * The experiment 
      setup is a bit hard to follow. It would be nice to be able to 
      understand this without referring to prior work. Can you elaborate a 
      bit on the application? It seems like you are trying to select 
      utterances which correspond to a small set of words, while trying to 
      capture the most variety in the utterances. Is this right? What is the 
      relevance of this problem?