11
$\begingroup$

Consider a ground set $U=\{1,2,...,n\}$ and the set $\mathcal{F}$ of all non-negative submodular functions $f: 2^U \mapsto \mathbb{R}_{\geq 0}$. The set $\mathcal{F}$ is closed under taking linear combinations of elements but with non-negative coefficients, and hence it forms a cone. Question: does this cone have $O(2^{poly(n)})$ number of extreme rays?

In other words, does there exist a set $\mathcal{B} \subseteq \mathcal{F}$ of non-negative submodular functions over $U$ such that any non-negative submodular function $f$ over $U$ can be represented as $f = \sum_{b\in \mathcal{B}} \gamma_b \cdot b$ for $\gamma_b \in \mathbb{R}_{\geq 0}$, and such that the size of $\mathcal{B}$ is exponential in $n$? I don't need a characterization of set $\mathcal{B}$, just quantify its size.

I came across this paper https://www.jstor.org/stable/1997813?seq=21#page_scan_tab_contents which in Section 2.1 states that such a cone has just $O(2^n\cdot n^2)$ facets, because we can define such a cone as an intersection of $O(2^n\cdot n^2)$ halfspaces each defined for a different triple $(X ,x,y) \subseteq 2^U \cdot U \cdot U$ by $f(X+x)+f(X+y)-f(X + x + y) -f(X) \geq 0$. I have a hard time reading the paper, so can someone tell me if this argument is already answering my question?

I will greatly appreciate any help.

EDIT: Would it change a lot, if we would be considering only monotone submodular functions?

$\endgroup$
  • 1
    $\begingroup$ A centrally symmetric polytope with polynomially many facets (in terms of dimension) must have exponentially many vertices. If you can intersect this cone with a hyperplane to get a polytope with a center of symmetry, then the extremal rays would correspond to vertices, and you will get an exponential in $2^n$ (i.e. doubly exponential) lower bound. But I have no clue if there is such symmetry here. $\endgroup$ – Sasho Nikolov Mar 27 '17 at 23:09
  • $\begingroup$ Thanks Sasho for answering, although I hope your argument doesn't work --- however unpolite it sounds;) I think that if it would work without any additional argumentation, i.e., only with the symmetry, then this could also work for some subclasses of submodular functions like alternating ones sciencedirect.com/science/article/pii/S0012365X16300267 Theorem 3.3, but for them there exist exponentially many rays. So I guess that doubly exponential lowerbound would require more work. Then again, it's just a loose thought of mine. $\endgroup$ – Marek Adamczyk Mar 27 '17 at 23:38
  • $\begingroup$ It's likely that the symmetry is not there. Note that for this argument you need two things: symmetry, and an exponential number of facets. $\endgroup$ – Sasho Nikolov Mar 28 '17 at 0:09
  • 2
    $\begingroup$ Just in case you find it useful: The paper Supermodular Functions on Finite Lattices by Promislow and Young (Order, 2005, 22:389), 10.1007/s11083-005-9026-5, doesn't talk about the size of \cal B but it gives precise characterisations of \cal B in interesting special cases. $\endgroup$ – Standa Zivny Apr 2 '17 at 12:45
  • $\begingroup$ Would it change a lot, if we would be considering only monotone submodular functions? $\endgroup$ – Marek Adamczyk Apr 3 '17 at 16:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.