Timezone: »

 
Poster
Submodular Maximization in Clean Linear Time
Wenxin Li · Moran Feldman · Ehsan Kazemi · Amin Karbasi

Tue Nov 29 02:00 PM -- 04:00 PM (PST) @ Hall J #812
in Poster Session 2 »
In this paper, we provide the first deterministic algorithm that achieves $1/2$-approximation for monotone submodular maximization subject to a knapsack constraint, while making a number of queries that scales only linearly with the size of the ground set $n$. Moreover, our result automatically paves the way for developing a linear-time deterministic algorithm that achieves the tight $1-1/e$ approximation guarantee for monotone submodular maximization under a cardinality (size) constraint. To complement our positive results, we also show strong information-theoretic lower bounds. More specifically, we show that when the maximum cardinality allowed for a solution is constant, no deterministic or randomized algorithm making a sub-linear number of function evaluations can guarantee any constant approximation ratio. Furthermore, when the constraint allows the selection of a constant fraction of the ground set, we show that any algorithm making fewer than $\Omega(n/\log(n))$ function evaluations cannot perform better than an algorithm that simply outputs a uniformly random subset of the ground set of the right size. We extend our results to the general case of maximizing a monotone submodular function subject to the intersection of a $p$-set system and multiple knapsack constraints. Finally, we evaluate the performance of our algorithms on multiple real-life applications, including movie recommendation, location summarization, Twitter text summarization, and video summarization.
Keywords: query complexity · Submodular maximization · cardinality constraint · p-set system constraint · Knapsack constraint · information-theoretic lower bound

Author Information

Wenxin Li (The Ohio State University)
Moran Feldman (University of Haifa)
Ehsan Kazemi (Yale Institute for Network Science, Yale)
Amin Karbasi (Yale University)

More from the Same Authors