Fast submodular maximization subject to k-extendible system constraints
Teng Li, Hyo‐Sang Shin, Antonios Tsourdos · arXiv (Cornell University) · 2018
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