Extensions and Ramifications of Discrete Convexity Concepts

Explore the extensions and ramifications of discrete convexity concepts in this comprehensive lecture by Kazuo Murota at the Hausdorff Center for Mathematics. Delve into the world of submodular functions and their recognition as discrete analogues of convex functions. Examine the evolution of discrete convex analysis, which broadens this perspective to encompass wider classes of discrete functions through the introduction of L-convex and M-convex functions defined on integer lattices. Investigate key issues in discrete convex analysis, including extensibility to real-variable convex functions, local characterization of global minimality, discrete duality concepts, and conjugacy relationships between L-convex and M-convex functions under Legendre-Fenchel transformation. Compare various related concepts proposed in literature, such as integrally-convex functions, M-convex functions on jump systems, and L-convex functions on graphs, evaluating their properties and motivations. Gain insights from this hour-long lecture, presented as part of the Hausdorff Trimester Program on Combinatorial Optimization.

Kazuo Murota: Extensions and Ramifications of Discrete Convexity Concepts