TY - ELEC
AU - Udwani, Rajan
PY - 2019
TI - Multi-objective Maximization of Monotone Submodular Functions with Cardinality Constraint
LA - eng
M3 - Moving Image
AB - We consider the problem of multi-objective maximization of monotone submodular functions subject to cardinality constraint, often formulated as $\max_{|A|=k}\min_{i\in\{1,\dots,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=\Omega(k)$, the problem is inapproximable (unless $P=NP$). We focus on the case where the number of objectives is super-constant yet much smaller than the cardinality of the chosen set. We propose the first constant factor algorithms for this regime, including one with the best achievable asymptotic guarantee and also a more practical nearly linear time algorithm. Experiments on synthetic data show that a heuristic based on our more practical and fast algorithm outperforms existing heuristics.
N2 - We consider the problem of multi-objective maximization of monotone submodular functions subject to cardinality constraint, often formulated as $\max_{|A|=k}\min_{i\in\{1,\dots,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=\Omega(k)$, the problem is inapproximable (unless $P=NP$). We focus on the case where the number of objectives is super-constant yet much smaller than the cardinality of the chosen set. We propose the first constant factor algorithms for this regime, including one with the best achievable asymptotic guarantee and also a more practical nearly linear time algorithm. Experiments on synthetic data show that a heuristic based on our more practical and fast algorithm outperforms existing heuristics.
UR - https://open.library.ubc.ca/collections/48630/items/1.0379889
ER - End of Reference