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|=kmin_i∈1,dots,mfi(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, Krause et al. (2008) showed that when the number of objectives m grows as the cardinality k i.e., m=Omega(k), the problem is inapproximable (unless P=NP). 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) nm/ε3. %In fact, the result of Chekuri et al. (2010) is for the far more general case of matroid constant. 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(fracklog3 k). This demonstrates a steep transition from constant factor approximability to inapproximability around m=Omega(k). Then using Multiplicative-Weight-Updates (MWU), we find a much faster tildeO(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 knm/ε4. Finally, we run synthetic experiments using Kronecker graphs and find that our MWU inspired heuristic outperforms existing heuristics.