Parametric monotone function maximization with matroid constraints

We study the problem of maximizing an increasing function \(f:2^N\rightarrow \mathcal {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\rightarrow \mathcal {R}_{+}\) be an increasing function with generic submodularity ratio \(\gamma \in (0,1]\), and let \((N,\mathcal {I})\) be a matroid. In this paper, we consider the problem \(\max _{S\in \mathcal {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.