On the Approximation of Submodular Functions

Understand

Submodular functions are a fundamental object of study in combinatorial optimization, economics, machine learning, etc.

• and exhibit a rich combinatorial structure.
• Many subclasses of submodular functions have also been well studied and these subclasses widely vary in their complexity.
• Our motivation is to understand the relative complexity of these classes of functions.