4
$\begingroup$

Is it possible to approximate a monotone submodular function using a concrete coverage function, i.e.

Given a ground set $U$ and a monotone submodular function, $f:2^U\to \mathbb{R}$, the goal is to find another ground set, $V$, and map each element from $U$ to a subset of $V$ ($m:U \to 2^V$) such that $f(S) \leq g(S) \leq \alpha f(S)$ for every $S \subseteq U$, where $\alpha$ is the approximation ratio (hopefully a constant) and $g(S) = c|\bigcup_{e \in S}m(e)|$ for some constant $c$.

An approximation that uses a weighted ground set, $V$, is also very welcomed (I guess we can't avoid that).

Thank you

$\endgroup$

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.