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?


closed as off-topic by Will Jagy, Alex Degtyarev, abx, Qiaochu Yuan, Stefan Kohl Feb 21 '15 at 9:45

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question does not appear to be about research level mathematics within the scope defined in the help center." – Will Jagy, Alex Degtyarev, abx, Qiaochu Yuan, Stefan Kohl
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 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 '15 at 13:56
  • 2
    $\begingroup$ meta.mathoverflow.net/a/2152/4600 $\endgroup$ – Bjørn Kjos-Hanssen Feb 21 '15 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 '15 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 '15 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 '15 at 17:23