Fast algorithms for supermodular and non-supermodular minimization via bi-criteria strategy

In this paper, we concentrate on exploring fast algorithms for the minimization of a non-increasing supermodular or non-supermodular function f subject to a cardinality constraint. As for the non-supermodular minimization problem with the weak supermodularity ratio r, we can obtain a $$(1+\epsilon )$$ ( 1 + ϵ ) -approximation algorithm with adaptivity $$O(\frac{n}{\epsilon }\log {\frac{r n \cdot f(\emptyset )}{\epsilon \cdot \mathtt {OPT}}})$$ O ( n ϵ log r n · f ( ∅ ) ϵ · OPT ) under the bi-criteria strategy, where $$\mathtt {OPT}$$ OPT denotes the optimal objective value of the problem. That is, instead of selecting at most k elements on behalf of the constraint, the cardinality of the output may reach to $$\frac{k}{ r}\log {\frac{f(\emptyset )}{\epsilon \cdot \mathtt {OPT}}}$$ k r log f ( ∅ ) ϵ · OPT . Moreover, for the supermodular minimization problem, we propose two $$(1+\epsilon )$$ ( 1 + ϵ ) -approximation algorithms for which the output solution X is of size $$|X_0|+ O\left( k \log {\frac{f(X_0)}{\epsilon \cdot \mathtt {OPT}}}\right) $$ | X 0 | + O k log f ( X 0 ) ϵ · OPT . The adaptivities of this two algorithms are $$O \left( \log ^2n \cdot \log \frac{f(X_0)}{\epsilon \cdot \mathtt {OPT}}\right) $$ O log 2 n · log f ( X 0 ) ϵ · OPT and $$O\left( \log n \cdot \log \frac{f(X_0)}{\epsilon \cdot \mathtt {OPT}}\right) $$ O log n · log f ( X 0 ) ϵ · OPT , where $$X_0$$ X 0 is an input set and $$\mathtt {OPT}$$ OPT is the optimal value. Applications to group sparse linear regression problems and fuzzy C-means problems are studied at the end.