Title: Submodular Knapsacks : A Discussion
Speaker: Prof. Avinash Bhardwaj, Dept. of Mechanical Engg, IITB.
Day, Date and Time: Monday, 4th July, 10 AM-11 AM
Venue: Seminar Room, IE 211, Second Floor, IEOR Building.
Abstract: A submodular (set) function is a set function whose value, informally, has the property that the difference in the incremental 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, modeling user preferences in game theoretic settings, machine learning and artificial intelligence with specific applications to summarization, feature selection, sensor placement etc.
In this discussion we will try to study the facial structure of the convex hull of the level sets of a given submodular set function f : {0,1}^n -> R. In particular we derive valid inequalities and their extensions for the general lower level sets of submodular set functions (not necessarily monotone) and propose (in some cases) facet defining conditions for the same. I will also highlight the connections that help us derive expressions for the valid inequalities and their extensions from the linear knapsack inequalities corresponding to the extended polymatroid of the set function in context.