Maximizing a submodular function of two sets with different size constraints

Question

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.

Answer 1

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.