Approximation for maximizing monotone non-decreasing set functions with a greedy method

We study the problem of maximizing a monotone non-decreasing function $$f$$ f subject to a matroid constraint. Fisher, Nemhauser and Wolsey have shown that, if $$f$$ f is submodular, the greedy algorithm will find a solution with value at least $$\frac{1}{2}$$ 1 2 of the optimal value under a general matroid constraint and at least $$1-\frac{1}{e}$$ 1 - 1 e of the optimal value under a uniform matroid $$(\mathcal {M} = (X,\mathcal {I})$$ ( M = ( X , I ) , $$\mathcal {I} = \{ S \subseteq X: |S| \le k\}$$ I = { S ⊆ X : | S | ≤ k } ) constraint. In this paper, we show that the greedy algorithm can find a solution with value at least $$\frac{1}{1+\mu }$$ 1 1 + μ of the optimum value for a general monotone non-decreasing function with a general matroid constraint, where $$\mu = \alpha $$ μ = α , if $$0 \le \alpha \le 1$$ 0 ≤ α ≤ 1 ; $$\mu = \frac{\alpha ^K(1-\alpha ^K)}{K(1-\alpha )}$$ μ = α K ( 1 - α K ) K ( 1 - α ) if $$\alpha > 1$$ α > 1 ; here $$\alpha $$ α is a constant representing the “elemental curvature” of $$f$$ f , and $$K$$ K is the cardinality of the largest maximal independent sets. We also show that the greedy algorithm can achieve a $$1 - (\frac{\alpha + \cdots + \alpha ^{k-1}}{1+\alpha + \cdots + \alpha ^{k-1}})^k$$ 1 - ( α + ⋯ + α k - 1 1 + α + ⋯ + α k - 1 ) k approximation under a uniform matroid constraint. Under this unified $$\alpha $$ α -classification, submodular functions arise as the special case $$0 \le \alpha \le 1$$ 0 ≤ α ≤ 1 .