TY - JOUR

T1 - Discrete Fenchel duality for a pair of integrally convex and separable convex functions

AU - Murota, Kazuo

AU - Tamura, Akihisa

N1 - Funding Information:
The authors thank Akiyoshi Shioura for a helpful comment, which led to Corollary?4.1 , and Satoru Fujishige for pointing out the connection to box convolution of bisubmodular functions mentioned in Sect.?3.1. This work was supported by JSPS/MEXT KAKENHI JP20K11697, JP16K00023, and JP21H04979.
Funding Information:
The authors thank Akiyoshi Shioura for a helpful comment, which led to Corollary , and Satoru Fujishige for pointing out the connection to box convolution of bisubmodular functions mentioned in Sect. . This work was supported by JSPS/MEXT KAKENHI JP20K11697, JP16K00023, and JP21H04979.
Publisher Copyright:
© 2022, The Author(s).

PY - 2022/5

Y1 - 2022/5

N2 - Discrete Fenchel duality is one of the central issues in discrete convex analysis. The Fenchel-type min–max theorem for a pair of integer-valued M♮-convex functions generalizes the min–max formulas for polymatroid intersection and valuated matroid intersection. In this paper we establish a Fenchel-type min–max formula for a pair of integer-valued integrally convex and separable convex functions. Integrally convex functions constitute a fundamental function class in discrete convex analysis, including both M♮-convex functions and L♮-convex functions, whereas separable convex functions are characterized as those functions which are both M♮-convex and L♮-convex. The theorem is proved by revealing a kind of box integrality of subgradients of an integer-valued integrally convex function. The proof is based on the Fourier–Motzkin elimination.

AB - Discrete Fenchel duality is one of the central issues in discrete convex analysis. The Fenchel-type min–max theorem for a pair of integer-valued M♮-convex functions generalizes the min–max formulas for polymatroid intersection and valuated matroid intersection. In this paper we establish a Fenchel-type min–max formula for a pair of integer-valued integrally convex and separable convex functions. Integrally convex functions constitute a fundamental function class in discrete convex analysis, including both M♮-convex functions and L♮-convex functions, whereas separable convex functions are characterized as those functions which are both M♮-convex and L♮-convex. The theorem is proved by revealing a kind of box integrality of subgradients of an integer-valued integrally convex function. The proof is based on the Fourier–Motzkin elimination.

KW - Discrete convex analysis

KW - Fenchel duality

KW - Fourier–Motzkin elimination

KW - Integral subgradient

KW - Integrally convex function

UR - http://www.scopus.com/inward/record.url?scp=85124165099&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85124165099&partnerID=8YFLogxK

U2 - 10.1007/s13160-022-00499-x

DO - 10.1007/s13160-022-00499-x

M3 - Article

AN - SCOPUS:85124165099

SN - 0916-7005

VL - 39

SP - 599

EP - 630

JO - Japan Journal of Industrial and Applied Mathematics

JF - Japan Journal of Industrial and Applied Mathematics

IS - 2

ER -