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

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