Generalized Submodular Optimization

Kimberly Yu (professeure adjointe, DIRO) — André-Aisenstadt 1207

22/03/2024 à 12h30

Submodularity is an important concept in integer and combinatorial optimization. Submodular set functions capture diminishing returns, and for this desirable property, they are found in numerous real-world applications. A submodular set function models the effect of selecting items from a single ground set, and whether an item is chosen can be modeled using a binary variable. However, in many problem contexts, our decisions involve choosing multiple copies of homogenous items, or heterogenous items from multiple sets. These scenarios give rise to generalizations of submodularity. In this talk, we will introduce such generalizations and discuss the theory and algorithms for the associated optimization problems.