Technical Program

Paper Detail

Paper IDA.3.1
Paper Title Concave Aspects of Submodular Functions
Authors Rishabh Iyer, University of Texas Dallas, United States; Jeff Bilmes, University of Washington, United States
Session A.3: Combinatorics and Information Theory
Presentation Lecture
Track Algebraic and Combinatorial Coding Theory
Manuscript  Click here to download the manuscript
Virtual Presentation  Click here to watch in the Virtual Symposium
Abstract Submodular Functions are a special class of Set Functions, which generalize several Information-Theoretic quantities such as Entropy and Mutual Information [1]. Submodular functions have subgradients and subdifferentials [2] and admit polynomial-time algorithms for minimization, both of which are fundamental characteristics of convex functions. Submodular functions also show signs similar to concavity. Submodular function maximization, though NP-hard, admits constant-factor approximation guarantees and concave functions composed with modular functions are submodular. In this paper, we try to provide a more complete picture of the relationship between submodularity with concavity. We characterize the super-differentials and polyhedra associated with upper bounds and provide optimality conditions for submodular maximization using the-super differentials.

Plan Ahead


2021 IEEE International Symposium on Information Theory

11-16 July 2021 | Melbourne, Victoria, Australia

Visit Website!