تقرير
Discrete Fenchel Duality for a Pair of Integrally Convex and Separable Convex Functions
| العنوان: | Discrete Fenchel Duality for a Pair of Integrally Convex and Separable Convex Functions |
|---|---|
| المؤلفون: | Murota, Kazuo, Tamura, Akihisa |
| سنة النشر: | 2021 |
| المجموعة: | Mathematics |
| مصطلحات موضوعية: | Mathematics - Combinatorics, 52A41, 90C27, 90C25 |
| الوصف: | 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-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-convex functions and L-natural-convex functions, whereas separable convex functions are characterized as those functions which are both M-natural-convex and L-natural-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. Comment: 32 pages |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2108.10502 |
| رقم الأكسشن: | edsarx.2108.10502 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |