I was interested in knowing about open research topics related with sub modularity, specially within its intersection with theoretical machine learning (and related topics).

It seems to me that much of what I've seen, specially related with greedy algorithms and theoretical guarantees has been solved. Is there anything open questions related with theoretical guarantees that is open in sub modularity?

  • 5
    $\begingroup$ Can someone explain why this was put on hold as off-topic? This question is about open problems in research-level mathematics! $\endgroup$
    – usul
    Feb 21, 2015 at 13:56
  • 2
    $\begingroup$ meta.mathoverflow.net/a/2152/4600 $\endgroup$ Feb 21, 2015 at 20:34
  • 3
    $\begingroup$ While the ultimate intent of the question is good, in its present form I think it is a bit too broad / vague. There are certainly several very specific open questions that do exist, including that of obtained "optimal" algorithms for submodular minimization, exploring connections to algebraic geometry, and much more. $\endgroup$
    – Suvrit
    Feb 21, 2015 at 22:27
  • 2
    $\begingroup$ I'm skeptical that the class of open questions in applications of submodularity to theoretical machine learning can be characterized as "broad", even if there are several answers. $\endgroup$
    – arsmath
    Feb 21, 2015 at 23:50
  • 1
    $\begingroup$ @Pinocchio, you can also try this question on cstheory.stackexchange.com, though I recommend trying to make it a bit more focused (for instance, if you care most about algorithms and optimization, mention that). $\endgroup$
    – usul
    Feb 23, 2015 at 17:23


Browse other questions tagged or ask your own question.