  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-\epsilon$)
for monotone submodular functions and of ($p(1-p)-\epsilon$) for non-monotone
cases with expected computational complexity of only
$O(\frac{pn}{\epsilon}\ln\frac{r}{\epsilon})$, where $r$ is the largest size of
the feasible solutions, $0<p \leq \frac{1}{1+k}$ is the sampling probability
and $0< \epsilon < 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}-\epsilon)$ and
$(\frac{k}{(1+k)^2}-\epsilon)$ respectively. While the parameter $\epsilon$
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.
