Abstract
We consider the problem of multi-objective maximization of monotone submodular functions subject to cardinality constraint, often formulated as max_|A|=kmin_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, Krause et al.\ (2008) showed that when the number of objectives m grows as the cardinality k i.e., m=Ω(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) n^m/ε³. %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(k/log³ 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 O(n/δ³) time asymptotic (1-1/e)²-δ approximation. While the above results are all randomized, we also give a simple deterministic (1-1/e)-ε approximation with runtime kn^m/ε⁴. Finally, we run synthetic experiments using Kronecker graphs and find that our MWU inspired heuristic outperforms existing heuristics.