Fast submodular maximization subject to k-extendible system constraints

Abstract

As the scales of data sets expand rapidly in some application scenarios, increasing efforts have been made to develop fast submodular maximization algorithms. This paper presents a currently the most efficient algorithm for maximizing general non-negative submodular objective functions subject to $k$-extendible system constraints. Combining the sampling process and the decreasing threshold strategy, our algorithm Sample Decreasing Threshold Greedy Algorithm (SDTGA) obtains an expected approximation guarantee of ($p-ε$) for monotone submodular functions and of ($p(1-p)-ε$) for non-monotone cases with expected computational complexity of only $O(\frac{pn}ε\ln\frac{r}ε)$, where $r$ is the largest size of the feasible solutions, $0<p \leq \frac{1}{1+k}$ is the sampling probability and $0< ε< p$. If we fix the sampling probability $p$ as $\frac{1}{1+k}$, we get the best approximation ratios for both monotone and non-monotone submodular functions which are $(\frac{1}{1+k}-ε)$ and $(\frac{k}{(1+k)^2}-ε)$ respectively. While the parameter $ε$ exists for the trade-off between the approximation ratio and the time complexity. Therefore, our algorithm can handle larger scale of submodular maximization problems than existing algorithms.

14 pages with no figure