Title: Efficient Algorithms and Lower Bound for Submodular Maximization

Authors: Wenxin Li, Ness Shroff


In this work, we study constrained submodular maximization problems and design algorithms that improve the state-of-the-art performance guarantees. We first present the \emph{adaptive decreasing threshold} algorithm, which achieves an approximation ratio of (1−1/e−ε) by performing queries per element. To the best of our knowledge, this is currently the fastest known \textbf{deterministic} algorithm, and nearly achieves the optimal approximation ratio. We also study several other well-known constrained monotone submodular maximization problems. First, for a single knapsack constraint, we propose an (7/16−ε)-approximate algorithm, which requires O(max{ε−1,loglogn}) queries per element and two passes in the streaming setting. This provides improvements in approximation ratio, query complexity and number of passes on the stream. Furthermore, we show that there is a (1/2−ε)-approximate deterministic algorithm for constant number of binary packing constraints, which only makes Oε(loglogn) queries per element. We next present an improved algorithm for the intersection of p-system and d knapsack constraint, which achieves an approximation ratio of 1/(p+74d+1)−ε. Query complexity lower bound of submodular maximization problems is also studied in this paper. We show that there exists no (randomized) (1/4+ϵ)-approximate algorithm using o(n/logn) queries for unconstrained submodular maximization. Combining with existing results, we present a complete characterization of the query complexity of unconstrained submodular maximization. To establish the lower bound, we introduce a general relationship between randomized and deterministic complexity of approximation algorithms.

Full Text: [PDF]

Accessibility at Yale   Inference, Information, and Decision Group at Yale