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.