Abstract:
We consider the problem of multi-objective maximization of monotone submodular functions subject to cardinality constraint, often formulated as max|A|=kmini∈{1,…,m}fi(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) 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(klog3k). 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/δ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.