Finding equivalent submodular function

89 Views Asked by At

Let $V$ be a finite set of points in $\mathbb{R}^n$ with $d(x,y)$ denoting the usual Euclidean distance between two points $x$ and $y$. I am trying to order points from the set $V$ iteratively, at each step picking the point $z$ that maximizes the following marginal gain with respect to the already picked points, which I denote by the set $X$ $$ f(z|X) = \frac{\sum_{y\in V} e^{-d(y,z)}}{1+ \sum_{x \in X} e^{-d(x,z)}}.$$

The idea is that we pick points which are close (similar) to all the points in our set (large nominator) and at the same time not too close to the already picked points (small denominator).

I was hoping that there is an underlying submodular function $f: 2^V \to \mathbb{R}$ such that the above defined marginal gain $f(z|X)$ can be expressed as the difference $$ f(z|X) = f(\{z\} \cup X) - f(X).$$

Unfortunately, trying to "build" $f$ incrementally by defining it first for the singletons, then for the two-element sets... led me to a contradiction. I don't know if I am doing something wrong, so my question, in case such a function cannot be defined, is whether we can come up with some other submodular function, name it $g$, that gives the same relative scores, i.e. the points picked $z_1 = \mbox{argmax}_{z\in V} f(z|\emptyset), z_2 = \mbox{argmax}_{z \in V\setminus\{z_1\}} f(z|\{z_1\}), z_3 = \mbox{argmax}_{z\in V\setminus\{z_1,z_2\}} f(z|\{z_1, z_2\})$,... will be the same as if we were picking them with the marginal gain induced by $g$ ?