Recent progress on integrally convex functions
Open Access
- 27 April 2023
- journal article
- research article
- Published by Springer Nature in Japan Journal of Industrial and Applied Mathematics
- Vol. 40 (3) , 1445-1499
Abstract
Integrally convex functions constitute a fundamental function class in discrete convex analysis, including M-convex functions, L-convex functions, and many others. This paper aims at a rather comprehensive survey of recent results on integrally convex functions with some new technical results. Topics covered in this paper include characterizations of integral convex sets and functions, operations on integral convex sets and functions, optimality criteria for minimization with a proximity-scaling algorithm, integral biconjugacy, and the discrete Fenchel duality. While the theory of M-convex and L-convex functions has been built upon fundamental results on matroids and submodular functions, developing the theory of integrally convex functions requires more general and basic tools such as the Fourier–Motzkin elimination.Keywords
All Related Versions
This publication has 57 references indexed in Scilit:
- Solving discrete systems of nonlinear equationsEuropean Journal of Operational Research, 2011
- Discrete fixed point theorem reconsideredJournal of Mathematical Economics, 2005
- Proximity theorems of discrete convex functionsMathematical Programming, 2004
- Conjugate Scaling Algorithm for Fenchel-Type Duality in Discrete Convex OptimizationSIAM Journal on Optimization, 2002
- Relationship of M-/L-convex functions with discrete convex functions by Miller and Favati–TardellaDiscrete Applied Mathematics, 2001
- b-matching degree-sequence polyhedraCombinatorica, 1991
- Directed submodularity, ditroids and directed submodular flowsMathematical Programming, 1988
- Operations that preserve total dual integralityOperations Research Letters, 1983
- A Fenchel-Rockafellar type duality theorem for maximizationBulletin of the Australian Mathematical Society, 1979
- A Min-Max Relation for Submodular Functions on Graphs1977