0
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ Did you check this work: proceedings.mlr.press/v48/baib16.html --- oops, that work is about minimization not maximization -- sorry! $\endgroup$ Commented Jun 29, 2021 at 15:15
  • $\begingroup$ Actually, I am aware of this work, and this is absolutely relevant, since Theorem 3.2 provides a way to get the $1-1/e$ approximation! What I want is to prove we can't (unless P=NP) do better $\endgroup$ Commented Jun 29, 2021 at 16:32

0

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.