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

• Kazuo Murota

• Akihisa Tamura

抄録

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 $$^{\natural }$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mrow /> <mml:mo>♮</mml:mo> </mml:msup> </mml:math> -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 $$^{\natural }$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mrow /> <mml:mo>♮</mml:mo> </mml:msup> </mml:math> -convex functions and L $$^{\natural }$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mrow /> <mml:mo>♮</mml:mo> </mml:msup> </mml:math> -convex functions, whereas separable convex functions are characterized as those functions which are both M $$^{\natural }$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mrow /> <mml:mo>♮</mml:mo> </mml:msup> </mml:math> -convex and L $$^{\natural }$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mrow /> <mml:mo>♮</mml:mo> </mml:msup> </mml:math> -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.

収録刊行物

• Japan Journal of Industrial and Applied Mathematics

  Japan Journal of Industrial and Applied Mathematics 39 (2), 599-630, 2022-02-02

  Springer Science and Business Media LLC

キーワード

• Applied Mathematics
• General Engineering

詳細情報

• CRID: 1360854009082264960
• NII論文ID: 210000165146
• DOI: 10.1007/s13160-022-00499-x
• ISSN: 1868937X
• ISSN: 09167005
• Web Site: https://link.springer.com/content/pdf/10.1007/s13160-022-00499-x.pdf
• Web Site: https://link.springer.com/article/10.1007/s13160-022-00499-x/fulltext.html
• データソース種別:
  • Crossref
  • CiNii Articles
  • KAKEN