9
$\begingroup$

Given a submodular function $f$ on $\Omega=X_1\cup X_2$ where $X_1$ and $X_2$ are disjoint and $f(S)=f_1(S\cap X_1)+f_2(S\cap X_2)$. Here $f_1$ and $f_2$ are submodular on $X_1$ and $X_2$ respectively.

Here $X_1,X_2,f_1,f_2$ are unknown and only a value query access to $f$ is given. Then is there a polytime algorithm which finds $X_1$. If there are multiple choices for $X_1$ any of them should be fine.

Some thoughts. If we can find any two elements $t_1,t_2$ such that both either belong to $X_1$ or belong to $X_2$ then we can merge them and proceed recursively. But it is not clear how to implement such a step.

$\endgroup$
  • 2
    $\begingroup$ Do you mean to say that $f(S) = f_1(S \cap X_1) + f_2(S \cap X_2)$ where $f_1$ and $f_2$ are submodular on $X_1$ and $X_2$ respectively? $\endgroup$ – Chandra Chekuri Nov 15 '11 at 4:56
  • $\begingroup$ Yes, I indeed meant that. Thanks for pointing the typo, I will correct it. $\endgroup$ – Ashwinkumar B V Nov 15 '11 at 5:23
  • 3
    $\begingroup$ I am not sure whether what I say below is correct but here is the idea. Take an arbitrary element $e \in \Omega$. If $f(e) = f_{\Omega-e}(e)$ then $e$ is not affected by the rest of the elements so we can choose $X_1 = \{e\}$ and $X_2 = \Omega-\{e\}$. Otherwise let $X$ be an inclusion-wise minimal subset of $\Omega-e$ such that $f(e) > f_X(e)$. Then it would seem that $X \cup \{e\}$ should be in the same partition and hence we can shrink the set into a single element and recurse if it is stricly smaller than $\Omega$, otherwise we conclude that no desired partition exists. $\endgroup$ – Chandra Chekuri Nov 15 '11 at 16:03
  • 2
    $\begingroup$ Decided to make the comment into an answer. $\endgroup$ – Chandra Chekuri Nov 18 '11 at 3:14
5
$\begingroup$

Take an arbitrary element $e \in \Omega$. If $f(e) = f_{\Omega-e}(e)$ then $e$ is not affected by the rest of the elements so we can choose $X_1 = \{e\}$ and $X_2 = \Omega-\{e\}$. Otherwise let $X$ be an inclusion-wise minimal subset of $\Omega-e$ such that $f(e) > f_X(e)$. Then $X \cup \{e\}$ should be in the same partition. If $X \cup \{e\} = \Omega$ we conclude that there is no desired partition, otherwise we shrink this set into a single element and recurse.

| cite | improve this answer | |
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.