Abstract 

We consider the problem of multi-objective maximization of monotone submodular functions subject to cardinality constraint, often formulated as max. 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., , the problem is inapproximable (unless P = N P ). On the other hand, when m is constant Chekuri et al. (2010) showed a randomized( ) approximation with runtime (number of queries to 3 function oracle) . 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 approximation for . 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 time asymptotic approximation. While the above results are all randomized, we also give a simple deterministic ( approximation with  runtime . Finally, we run synthetic experiments using Kronecker graphs and find that our MWU inspired heuristic outperforms existing heuristics.