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

Abstract

We study the problem of maximizing a monotone non-decreasing function {Mathematical expression} subject to a matroid constraint. Fisher, Nemhauser and Wolsey have shown that, if {Mathematical expression} is submodular, the greedy algorithm will find a solution with value at least {Mathematical expression} of the optimal value under a general matroid constraint and at least {Mathematical expression} of the optimal value under a uniform matroid {Mathematical expression}, {Mathematical expression}) constraint. In this paper, we show that the greedy algorithm can find a solution with value at least {Mathematical expression} of the optimum value for a general monotone non-decreasing function with..