<p>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. </p>

CC BY-SA 3.0
2012-10-10T01:52:37.707Z
2012-10-10T01:52:37.707Z
Chandra Chekuri
<p>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.</p>

<p>$f(S,T)$ has the following interesting properties:</p>

<ul>
<li><p>fixing $T$, it is non-negative, submodular and monotone w.r.t. $S$;</p></li>
<li><p>fixing $S$, it is non-negative, submodular and monotone w.r.t. $T$.</p></li>
</ul>

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

<p>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|$.</p>

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

CC BY-SA 3.0
2012-10-09T17:26:45.773Z
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$.
Colin McQuillan
CC BY-SA 3.0
2012-10-09T19:27:54.557Z
Thanks, good point. So, let's forget the second part of my question. Any idea about how to maximize such a function?
Francesco Bonchi
<ds.algorithms><optimization><submodularity>
Maximizing a submodular function of two sets with different size constraints
Francesco Bonchi
# Maximizing a submodular function of two sets with different size constraints

(Asked by: username_0 on 2012-10-09)

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.

**Tags:** ds.algorithms, optimization, submodularity

> **Comments:**
> **username_1**: 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$.  
> **username_0**: Thanks, good point. So, let's forget the second part of my question. Any idea about how to maximize such a function?  

---

## 1 answers

### Answer by username_2 on 2012-10-10. Score: 10 | Accepted answer

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.


---

