Parametric monotone function maximization with matroid constraints

We study the problem of maximizing an increasing function $$f:2^N\rightarrow \mathcal {R}_{+}$$ f : 2 N → R + subject to matroid constraints. Gruia Calinescu, Chandra Chekuri, Martin Pál and Jan Vondrák 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$$ 1 - 1 / e of the optimal value. But pipage rounding technique have strong requirement for submodularity. Chandra Chekuri, Jan Vondrák 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$$ 1 - 1 / e times of the value of the fractional solution. Let $$f:2^N\rightarrow \mathcal {R}_{+}$$ f : 2 N → R + be an increasing function with generic submodularity ratio $$\gamma \in (0,1]$$ γ ∈ ( 0 , 1 ] , and let $$(N,\mathcal {I})$$ ( N , I ) be a matroid. In this paper, we consider the problem $$\max _{S\in \mathcal {I}}f(S)$$ max S ∈ I f ( S ) and provide a $$\gamma (1-e^{-1})(1-e^{-\gamma }-o(1))$$ γ ( 1 - e - 1 ) ( 1 - e - γ - 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.