Submodular Set Function

A Submodular Set Function is a set function where the difference in the value of the function that a single element makes when added to an input set decreases as the size of the input set increases.

• • …
• Counter-Example(s):
  • Supermodular Function.
  • Modular Function.
  • Convex Function.
• See: Submodular Optimization, Diminishing Returns, Approximation Algorithm, Greedy Algorithm, Finite Set, Shared Fixed Costs, Matroid Rank Function, Submodular Set Cover Task, Difference of Submodular Function, Graph Cut Function.

---

---

References

2015

• (Wikipedia, 2015) ⇒ http://en.wikipedia.org/wiki/submodular_set_function Retrieved:2015-1-26.
  • In mathematics, a submodular set function (also known as a submodular function) is a set function whose value, informally, has the property that the difference in the value of the function that a single element makes when added to an input set decreases as the size of the input set increases. Submodular functions have a natural diminishing returns property which makes them suitable for many applications, including approximation algorithms, game theory (as functions modeling user preferences) and electrical networks.

2014

• http://submodularity.org/
  • QUOTE: This page collects some material and references related to submodular optimization, with applications in particular in machine learning and AI. Convex optimization has become a main workhorse for many machine learning algorithms during the past ten years. When minimizing a convex loss function for, e.g., training a Support Vector Machine, we can rest assured to efficiently find an optimal solution, even for large problems. In recent years, another fundamental problem structure, which has similar beneficial properties, has emerged as very useful in a variety of machine learning applications: Submodularity is an intuitive diminishing returns property, stating that adding an element to a smaller set helps more than adding it to a larger set. Similarly to convexity, submodularity allows one to efficiently find provably (near-)optimal solutions.

2014

• (Badanidiyuru et al., 2014) ⇒ Ashwinkumar Badanidiyuru, Baharan Mirzasoleiman, Amin Karbasi, and Andreas Krause. (2014). “Streaming Submodular Maximization: Massive Data Summarization on the Fly.” In: Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ISBN:978-1-4503-2956-9 doi:10.1145/2623330.2623637

2013

• (Krause & Guestrin, 2013) ⇒ Andreas Krause, and Carlos Guestrin. (2013). “Submodularity in Machine Learning: New Directions." Tutorial at ICML 2013.

2010

• (Lin & Bilmes, 2010) ⇒ Hui Lin, and Jeff Bilmes. (2010). “Multi-document Summarization via Budgeted Maximization of Submodular Functions.” In: Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics. ISBN:1-932432-65-5

2008

• (Krause & Guestrin, 2008) ⇒ Andreas Krause, and Carlos Guestrin. (2008). “Beyond Convexity - Submodularity in Machine Learning." Tutorial at ICML 2008.

2008

• (Krause & Guestrin, 2008) ⇒ A. Krause, and C. Guestrin. (2008). “Beyond Convexity - Submodularity in Machine Learning.” In: ICML, 2008.

1988

• (Nemhauser & Wolsey, 1988) ⇒ George L. Nemhauser, and Laurence A. Wolsey. (1988). “Integer and Combinatorial Optimization." Wiley.
• Lovasz ...

1978

• (Topkis, 1978) ⇒ Donald M. Topkis. (1978). “Minimizing a Submodular Function on a Lattice.” In: Operations Research, 26(2).

---