Parametric monotone function maximization with matroid constraints

We study the problem of maximizing an increasing function f : 2(N) -> R+ subject to matroid constraints. Gruia Calinescu, Chandra Chekuri, Martin Pal and Jan Vondrak have shown that, if f is nondecreasing and submodular, the continuous greedy algorithm and pipage rounding technique can be combined to find a solution with value at least 1 - 1/e of the optimal value. But pipage rounding technique have strong requirement for submodularity. Chandra Chekuri, Jan Vondrak and Rico Zenklusen proposed a rounding technique called contention resolution schemes. They showed that if f is submodular, the objective value of the integral solution rounding by the contention resolution schemes is at least 1- 1/e times of the value of the fractional solution. Let f : 2(N) -> R+ be an increasing function with generic submodularity ratio gamma is an element of (0, 1], and let (N, I) be a matroid. In this paper, we consider the problem max(S is an element of I) f (S) and provide a gamma(1-e(-1))(1-e(-gamma) - o(1))-approximation algorithm. Our main tools are the continuous greedy algorithm and contention resolution schemes which are the first time applied to nonsubmodular functions.