Deterministic approximation algorithm for submodular maximization subject to a matroid constraint (Q2235731)

The paper studies the generalized submodular maximization problem over a base set \(N\) with a non-negative monotone submodular set function \(f:2^N\rightarrow\mathbb{R}_{\ge 0}\) as the objective function and subject to a matroid constraint. The aim is to seek a subset \(S\) of \(N\), simultaneously satisfying the feasibility constraint of the matroid \(\mathcal{M}\) and maximizing the value of \(f\). The problem is generalized through the curvature parameter \(\alpha\in[0, 1]\) and we say that a submodular function \(f\) is with curvature \(\alpha\), if \(f(S\cup\{s\})-f(S)\ge(1-\alpha)f(\{s\})\) holds for any subset \(S\subset N\) and element \(s\in N\setminus S\). The main result is a deterministic approximation algorithm for the above problem. The algorithm employs the deterministic algorithm devised by \textit{N. Buchbinder} et al. [in: Proceedings of the 30th annual ACM-SIAM symposium on discrete algorithms, SODA 2019. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 241--254 (2019; Zbl 1431.90125)] as a building block and it reaches the same ratio of 0.5008 when the curvature parameter \(\alpha = 1\), and approximation ratio 1 when \(\alpha = 0\). For a calibrating parameter \(y\in[0,1]\) the algorithm achieves the following approximation ratio: \[ \frac{1 + h_\alpha(y) +\Delta\cdot[3 + \alpha-(2 + \alpha)y-(1 + \alpha)h_\alpha(y)]}{2 + \alpha + (1 + \alpha)(1-y)}, \] where \(h_\alpha(y)\doteq\frac{1-(1-y)^{1+\alpha}}{1+\alpha}\).