2

A function $f: \mathbb{R}^2 \to \mathbb{R}$ is said to be submodular if for all $x,y \in \mathbb{R}^2$ it holds $$ f(x \vee y)+f(x \wedge y)\le f(x)+f(y). $$

In particular, if $x_1 \ge y_1$ and $x_2 \le y_2$, this means that $$ f(y_1,x_2)+f(x_2,y_1) \le f(x_1,y_1)+f(x_2,y_2), $$ or, equivalently, $$ \sum_{I\subseteq \{1,2\}}(-1)^{|I|}f(xIy)\ge 0 $$ where $xIy$ is the vector $I$ where we replace the components of $x$ with the components of $y$ in the positions in $I$.

Question. Let us take a function $f:\mathbb{R}^3 \to \mathbb{R}$ with the property that $$ \sum_{I\subseteq \{1,2,3\}}(-1)^{|I|}f(xIy)\ge 0 $$ for all vector $x,y \in \mathbb{R}^3$. Do such function have a name in the literature?

1 Answers1

1

I don't know about the functions that you've described here, but a related concept is something termed "continuous submodlarity", which is a way to extend the notions of submodularity to $\mathbb{R}^n$. The idea is to use the lattice on $\mathbb{R}_n$ obtained by component-wise partial ordering.

For $i=1, \dots n$, let $\mathcal{X}_i$ be a compact subset of $\mathbb{R}$ (i.e. an interval $[a,b]$ or a finite set $\{ 0, 1 \}$) and let $\mathcal{X} = \prod_{i=1}^n \mathcal{X_i} \subset \mathbb{R}^n$ be the product. Given two vectors $x,y \in \mathcal{X}$, define $x \vee y$ to be a component-wise maximum and $x \wedge y$ to be component-wise minimum. A function $f: \mathcal{X} \rightarrow \mathbb{R}$ is continuous submodular if for all $x,y \in \mathcal{X}$, we have $$ f(x \vee y) + f(x \wedge y) \leq f(x) + f(y)$$

Here's a 2015 paper by Bach which describes these functions in the context of minimization. Here's a 2019 paper by Rad Niazadeh, Tim Roughgarden, and Joshua R. Wang which gives (what I believe is) the first non-trivial maximization algorithm for this function class.

Chris Harshaw
  • 1,124