5
$\begingroup$

If I have a function which is convex in the hypercube, $[-1,1]^n$ then when would it imply that its restriction to $\{-1,1\}^n$ is submodular?

  • It would be helpful is someone can share some specific example calculation! (better if you have examples with spectral norms which is a convex function!)

(..I am implicitly assuming the picture that a function on the Boolean hypercube can always be thought of as a function on the powerset of the set $\{1,2,..,n\}$. The numbers in any element of the powerset specifies the indices of the domain vector which have 1 (and the rest will have -1)...)

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

Check out page 15 in this paper from 1983:

http://www.cs.elte.hu/~lovasz/scans/submodular.pdf

It says that the restriction of a convex function to a binary domain, does not necessarily yield a submodular function.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .