Sum of Squares Submodularity
Certifying Submodularity with Algebraic Techniques Submodularity is a structural property encoding the notion of diminishing returns, that is, the benefits one gets from an additional element decrease when many elements have been chosen. This property appears in many applications, from operations research to machine learning and economics. Unfortunately, testing whether a set function is submodular is computationally intractable for set functions of degree 4 or higher. In “Sum of Squares Submodularity,” Anna Deza and Georgina Hall introduce the notion of t-sum of squares submodularity, a hierarchy of algebraic certificates that provides tractable sufficient conditions for submodularity. For each fixed level t, membership in the hierarchy can be checked through semidefinite programming. The paper develops equivalent characterizations of the hierarchy, identifies operations that preserve it, and clarifies when it coincides with submodularity. It also demonstrates practical value in three settings: submodular regression, bounding submodularity ratios for approximate maximization, and constructing improved difference of submodular decompositions.
- DOI
- 10.1287/opre.2025.2422
- Language
- en
- Export
- BibTeX
- Sources
- crossref