Note on the polyhedral description of the Minkowski sum of two L-convex sets
Note on the polyhedral description of the Minkowski sum of two L-convex sets
复制标题
关于两个 L 凸集的 Minkowski 和的多面体描述的注记
DOI：
10.1007/s13160-022-00512-3
复制
发表时间：
2022
影响因子：
0.9
通讯作者：
Murota Kazuo
中科院分区：
文献类型：
--
作者：
Moriguchi Satoko;Murota Kazuo
L-凸集是离散凸分析中最基本的概念之一。此外，两个L-凸集的Minkowski和，称为L-凸集，是一个有趣的对象，与多拟阵交密切相关。本文给出了L-凸集的多面体描述，并观察到L-凸集的凸船体是盒TDI多面体。对多面体描述给出了两种不同的证明。第一个是一个结构简短的证明，依赖于共轭定理在离散凸分析，第二个是一个直接的代数证明，基于傅立叶-Motzkin消除。所得到的结果承认自然图表示。所得结果在离散凸分析中的意义也进行了讨论。
L-convex sets are one of the most fundamental concepts in discrete convex analysis. Furthermore, the Minkowski sum of two L-convex sets, called L-convex sets, is an intriguing object that is closely related to polymatroid intersection. This paper reveals the polyhedral description of an L-convex set, together with the observation that the convex hull of an L-convex set is a box-TDI polyhedron. Two different proofs are given for the polyhedral description. The first is a structural short proof, relying on the conjugacy theorem in discrete convex analysis, and the second is a direct algebraic proof, based on Fourier–Motzkin elimination. The obtained results admit natural graph representations. Implications of the obtained results in discrete convex analysis are also discussed.
登录
查看更多内容
数学工程技术报告 Dijkstra 算法和 L 凹函数最大化
DOI：
--
发表时间：
2012
期刊：
--
影响因子：
--
作者：
K. Murota;A. Shioura
通讯作者：
A. Shioura
DOI：
10.1007/s13160-020-00416-0
发表时间：
2020-01
影响因子：
0.9
作者：
A. Tamura;Kazuya Tsurumi
通讯作者：
A. Tamura;Kazuya Tsurumi
Miller 和 Favati-Tardella 的 M/L 凸函数与离散凸函数的关系
DOI：
10.1016/s0166-218x(01)00222-0
发表时间：
2001
期刊：
Discret. Appl. Math.
影响因子：
--
作者：
K. Murota;A. Shioura
通讯作者：
A. Shioura
DOI：
--
发表时间：
2019
期刊：
影响因子：
--
作者：
Akiyoshi Shioura
通讯作者：
Akiyoshi Shioura
影响因子：
5
作者：
Xin Chen;Menglong Li
通讯作者：
Xin Chen;Menglong Li