Multi-objective Maximization of Monotone Submodular Functions with Cardinality Constraint
We consider the problem of multi-objective maximization of monotone submodular functions subject to cardinality constraint, often formulated as max |A|=k min i∈{1,...,m} f i (A). While it is widely known that greedy methods work well for a single objective, the problem becomes much harder with multiple objectives. In fact,  showed that when the number of objectives m grows as the cardinality k i.e., m = Ω(k), the problem is inapproximable (unless P = N P ). On the other hand, when m is constant Chekuri et al. (2010) showed a randomized (1 − 1/e) − approximation with runtime (number of queries to function oracle) n m/ 3 . We focus on finding a fast and practical algorithm that has (asymptotic) approximation guarantees even when m is super constant. We first modify the algorithm of Chekuri et al. (2010) to achieve a (1 − 1/e) − approximation for m = o( k log 3 k ), with → 0 as k → ∞. This demonstrates a steep transition from constant factor approximability to inapproximability around m = Ω(k). Then using Multiplicative-Weight-Updates (MWU), we find a much fasterÕ(n/δ 3 ) time asymptotic (1 − 1/e) 2 − δ approximation. While the above results are all randomized, we also give a simple deterministic (1 − 1/e) − approximation with runtime kn m/ 4 . Finally, we run synthetic experiments using Kronecker graphs and find that our MWU inspired heuristic outperforms existing heuristics.
The paper studies a robust formulation of maximizing a submodular function subject to a cardinality constraint. Specifically, the goal is to maximize the minimum of m submodular functions f_1,..., f_m subject to picking at most k elements. When there is no restriction on k and m, the problem can be hard to approximate. The paper focuses on the regime where m << k and in this regime, it is possible to avoid the hardness and obtain approximation solution.  The algorithm is inspired by previous work by CCPV'07. Previously the algorithm needs to guess the elements with large value because rounding only works when all elements have small values. Furthermore, previous work focused on getting polynomial time and uses a slow continuous greedy approach. To address the first problem, the paper focuses on a special case m<
Reviewer 3
The paper proposes three efficient multiobjective submodular maximization algorithms.  I like this paper, and has no clear objection to the paper. The techniques (using one-pass procedure for picking the heavy elements, separating MWU and the continuous greedy) are simple and effective, and seem to be applied for more general problems.    [minor] - l.21: The first paragraph (many well known ...) is arguable. There are many non-submodular combinatorial optimization problems.  - l.60: the approximation ratio of multilinear extension-based method must be (1 - 1/e) - \epsilon. - l.89: Please write the complexity of (1 - 1/e) approx algorithm explicitly. I think it already gives significant improvement from n^{O(1/eps)} to O(poly(n, 1/eps)), and the actual bottleneck of Algorithm 1 is this factor (usually it exceeds n^{100}). - l.129: it wil be better to write x = (x_1, ..., x_n) instead of x = {x_1, ...,x_n}.  [very minor] - l.129: I guess you used $$ ... $$ for the display math. As in https://nips.cc/Conferences/2018/PaperInformation/StyleFiles it should be avoided because it breaks line numbering.