Open AccessMultiobjective Maximization of Monotone Submodular Functions with Cardinality Constraint
Author(s) -
Rajan Udwani
Publication year - 2021
Publication title -
informs journal on optimization
Language(s) - English
Resource type - Journals
eISSN - 2575-1492
pISSN - 2575-1484
DOI - 10.1287/ijoo.2019.0041
Subject(s) - submodular set function , cardinality (data modeling) , mathematics , approximation algorithm , combinatorics , monotone polygon , constant (computer programming) , discrete mathematics , multiplicative function , maximization , greedy algorithm , function (biology) , oracle , mathematical optimization , computer science , geometry , software engineering , evolutionary biology , data mining , programming language , mathematical analysis , biology
We consider the problem of multiobjective maximization of monotone submodular functions subject to cardinality constraint, often formulated as [Formula: see text]. 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, [Formula: see text], the problem is inapproximable (unless P = NP). On the other hand, when m is constant, there exists a a randomized [Formula: see text] approximation with runtime (number of queries to function oracle) the scales as [Formula: see text]. 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 [Formula: see text] approximation for [Formula: see text]. This demonstrates a steep transition from constant factor approximability to inapproximability around [Formula: see text]. Then using multiplicative-weight-updates (MWUs), we find a much faster [Formula: see text] time asymptotic [Formula: see text] approximation. Although these results are all randomized, we also give a simple deterministic [Formula: see text] approximation with runtime [Formula: see text]. Finally, we run synthetic experiments using Kronecker graphs and find that our MWU inspired heuristic outperforms existing heuristics.