Multiobjective Maximization of Monotone Submodular Functions with Cardinality Constraint

We consider the problem of multiobjective maximization of monotone submodular functions subject to cardinality constraint, often formulated as ${\max }_{\left|A\right|=k}{\min }_{i\in \left\{1,\mathrm{\dots },m\right\}}{f}_i\left(A\right)$. Although it is widely known that greedy methods work well for a single objective, the problem becomes much harder with multiple objectives. In fact, it is known that when the number of objectives m grows as the cardinality k, that is, $m=\Omega \left(k\right)$, the problem is inapproximable (unless P = NP). On the other hand, when m is constant, there exists a a randomized $\left(1-1/e\right)-\epsilon$ approximation with runtime (number of queries to function oracle) the scales as $n^{m/{\epsilon }^3}$. We focus on finding a fast algorithm that has (asymptotic) approximation guarantees even when m is super constant. First, through a continuous greedy based algorithm we give a $(1-1/e)$ approximation for $m=o\left(\frac{k}{{\log }^{3}k}\right)$. This demonstrates a steep transition from constant factor approximability to inapproximability around $m=\Omega \left(k\right)$. Then using multiplicative-weight-updates (MWUs), we find a much faster $\tilde{O}\left(n/{\delta }^3\right)$ time asymptotic ${\left(1-1/e\right)}^2-\delta$ approximation. Although these results are all randomized, we also give a simple deterministic $\left(1-1/e\right)-\epsilon$ approximation with runtime $k{n}^{m/{\epsilon }^4}$. Finally, we run synthetic experiments using Kronecker graphs and find that our MWU inspired heuristic outperforms existing heuristics.