*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
TITLE: Submodular Knapsacks - A Polyhedral Discussion
ABSTRACT:
Submodular and supermodular knapsack sets arise naturally when modeling utilities, risk and probabilistic constraints on discrete variables. Although submodular functions have been explored plentiful with respect to set function optimization, understanding of level sets of these set functions is still underdeveloped. The results with respect to submodular optimization cannot be translated as such when optimizing over the level sets of submodular functions. In particular, even though the convex hull of convex lower envelope of a general submodular function f can be completely characterized, the convex hull description of the lower level set of f is unknown even in the special case when f is monotone. In this talk, we will study the facial structure of the convex hull of the level sets of a given (not necessarily monotone) submodular set function f : {0, 1}^n
