Parametric monotone function maximization with matroid constraints

• DOI: 10.1007/s10898-019-00800-2
• Publication Date: 2019-07-03T13:02:53Z
• Authors: Suning Gong; Qingqin Nong; Wenjing Liu; Qizhi Fang
• Keywords: 0211 other engineering and technologies; 02 engineering and technology

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.