Given a non-decreasing, normalized, submodular function $f : 2^{[n]}\mapsto \mathbb{R}_+$ and a modular non-decreasing function $g$, I am wondering what is the best approximation ratio I can hope for maximizing $f\over g$. I think the answer is $1-1/e$, using a reduction from the particular problem $$\max {f(S) \over |S| + c}, \quad\text{ given }c>0,$$ to the standard $k$-cardinality constraint maximization of $f$, for a particular choice of $c=c_k$. However, this is not so clear how to do this reduction... here is my attempt (that only reduces to a randomized version):
Suppose we have an $\alpha-$approx algo $A:c \mapsto A(c)\in 2^{[n]}$ for the above problem. The function $c\mapsto \max_{c'\in \mathbb{R}_+}{f(A(c'))\over |A(c')| + c}$ is continuous and non-increasing, and we can evaluate it using a linear search. Plus, $c\mapsto |A(\text{argmax}_{c'\in \mathbb{R}_+}{f(A(c'))\over |A(c')| + c})|$ is non-increasing, so we can use a binary search to find a value $c^*$ such that either $|A(\text{argmax}_{c'\in \mathbb{R}_+}{f(A(c'))\over |A(c')| + c^*})|=k$ or $\text{argmax}_{c'\in \mathbb{R}_+}{f(A(c'))\over |A(c')| + c^*}$ is not a singleton and contains 2 values $c_1,c_2$ with $|A(c_1)|<k<|A(c_2)|$. In any case, we can find a randomized solution $S$ of averaged cardinality $k$ that satisfies $${\mathbb{E}[f(S)]\over k + c^*} = {\mathbb{E}[f(S)]\over \mathbb{E}[|S|] + c^*}\geq {f(A(c^*))\over |A(c^*)| + c^*} \geq \alpha \max_{S^*\in 2^{[n]}, |S^*|=k}{f(S^*)\over |S^*| + c^*} = \alpha \max_{S^*\in 2^{[n]}, |S^*|=k}{f(S^*)\over k + c^*} $$
My main goal is to get a randomisation-free reduction.