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

Kazuo Murota, Akihisa Tamura

Research output: Contribution to journalArticlepeer-review

4 Citations (Scopus)


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.

Original languageEnglish
Pages (from-to)599-630
Number of pages32
JournalJapan Journal of Industrial and Applied Mathematics
Issue number2
Publication statusPublished - 2022 May


  • Discrete convex analysis
  • Fenchel duality
  • Fourier–Motzkin elimination
  • Integral subgradient
  • Integrally convex function

ASJC Scopus subject areas

  • General Engineering
  • Applied Mathematics


Dive into the research topics of 'Discrete Fenchel duality for a pair of integrally convex and separable convex functions'. Together they form a unique fingerprint.

Cite this