This week I will be talking about submodular set functions, which possess a useful and intuitive diminishing returns property. I will begin with the definition and give a variety of examples of situations in which submodular functions arise. I'll discuss some connections to convex and concave functions, as well as strategies for minimization and maximization. I will mainly draw from the classic paper "Submodular functions and convexity" by Lovász, as well as a recent paper by Stobbe and Krause, which provides a nice summary of key results, as well as a discussion of many of the advances since the Lovász paper. If the talk sparks your interest, then I highly recommend the tutorial (complete with hours of video!) by Krause and Guestrin.
No comments:
Post a Comment
Note: Only a member of this blog may post a comment.