Submodularity for Cartesian product

172 Views Asked by At

We define a set function $f:2^E \rightarrow \mathbb{R}$ to be submodular if for every $ S,T\subseteq E $ with $ S\subseteq T $ and for every $ x\in E\setminus T : f(S\cup \{x\})-f(S)\geq f(T\cup\{x\}) - f(T) $.

How could I extend this concept to a Cartesian product of two sets? For example, would the following definition make sense?

We define a set function $f:2^{E_1 \times E_2} \rightarrow \mathbb{R}$ to be submodular if for every $ S_1,T_1\subseteq E_1 $ with $ S_1\subseteq T_1 $ and $ S_2,T_2\subseteq E_2 $ with $ S_2\subseteq T_2 $ for every $ p\in E_1\setminus T_1$ and $q\in E_2\setminus T_2 $, it holds that $f((S_1\cup \{p\}) \times (S_2\cup \{q\}))-f(S_1 \times S_2)\geq f((T_1\cup \{p\}) \times (T_2\cup \{q\})) - f(T_1 \times T_2) $.

If yes, then how can I prove this holds if submodularity holds for individual set functions $f_1:2^{E_1} \rightarrow \mathbb{R}$ and $f_2:2^{E_2} \rightarrow \mathbb{R}$?

Any help and hints will be greatly appreciated.