8
$\begingroup$

I have two totally distinct domains (apples and oranges) and I have a function $f$ that takes a set of objects from the first domain and a set of objects from the second domain and returns a real number.

$f(S,T)$ has the following interesting properties:

  • fixing $T$, it is non-negative, submodular and monotone w.r.t. $S$;

  • fixing $S$, it is non-negative, submodular and monotone w.r.t. $T$.

I want to maximize $f(S,T)$ with two cardinality constraints $|S| = s$ and $|T| = t$.

How can I do that? If I consider the product space, the function is monotone and submodular. Thus I can apply the standard greedy algorithm. Dealing with the two different size constraints, might not be an issue: adding $(a, x)$ and $(a, y)$ in sequence allows me to increase $|T|$ without increasing $|S|$.

The question is whether the $1-1/e$ approximation still holds.

$\endgroup$
  • 4
    $\begingroup$ Those two properties do not imply submodularity on the product space, for example $f(\emptyset,\emptyset)=f(\{s\},\emptyset)=f(\emptyset,\{t\})=0$ and $f(\{s\},\{t\})=1$. $\endgroup$ – Colin McQuillan Oct 9 '12 at 17:26
  • 2
    $\begingroup$ Thanks, good point. So, let's forget the second part of my question. Any idea about how to maximize such a function? $\endgroup$ – Francesco Bonchi Oct 9 '12 at 19:27
10
$\begingroup$

The problem is likely to be hard to approximate. The densest bipartite subgraph problem can be cast as a special case. Given a bipartite graph $(V,E)$ where $V=V_1 \uplus V_2$ define $f(S,T)$ for $S \subseteq V_1, T \subseteq V_2$ to be the number of edges between $S$ and $T$. Then $f$ satisfies the desired property. In fact $f(S,\cdot)$ is modular and so is $f(\cdot,T)$. If $a=b=k$ then we are asking for a $k$ by $k$ densest bipartite subgraph problem. Only a polynomial ratio approximation is known, and under some assumptions this problem can be shown to be hard.

$\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.