Decreasing minimization on base-polyhedra: Relation between discrete and continuous cases
Decreasing minimization on base-polyhedra: Relation between discrete and continuous cases
复制标题
基多面体的递减最小化：离散情况和连续情况之间的关系
DOI：
10.1007/s13160-022-00511-4
复制
发表时间：
2023
影响因子：
0.9
通讯作者：
K. Murota
中科院分区：
文献类型：
--
作者：
A. Frank;K. Murota
研究了基多面体上离散最小化问题与连续最小化问题的关系。连续版本（以多矩阵的字典学最优基的名义）在1980年由Fujishige解决，随后的详细描述在他的书（1991）中。deci -min问题（关于m -凸集）的离散对应问题最近才得到解决，用一种强多项式算法不仅可以计算单个递减最小元，而且可以计算所有递减最小元的矩阵结构和称为正则划分的对偶对象。本文的目的是通过建立新的技术成果和对已知成果的整合，对基多面体上的连续和离散十分问题之间的关系提供一个完整的图景。特别地，我们通过揭示主划分和正则划分之间的关系，得到了在连续和离散情况下最小元素的几何接近性的近似结果。我们还根据Fujishige和Groenevelt的方法描述了离散情况下的分解型算法。
This paper is concerned with the relationship between the discrete and the continuous decreasing minimization problem on base-polyhedra. The continuous version (under the name of lexicographically optimal base of a polymatroid) was solved by Fujishige in 1980, with subsequent elaborations described in his book (1991). The discrete counterpart of the dec-min problem (concerning M-convex sets) was settled only recently by the present authors, with a strongly polynomial algorithm to compute not only a single decreasing minimal element but also the matroidal structure of all decreasing minimal elements and the dual object called the canonical partition. The objective of this paper is to offer a complete picture on the relationship between the continuous and discrete dec-min problems on base-polyhedra by establishing novel technical results and integrating known results. In particular, we derive proximity results, asserting the geometric closeness of the decreasingly minimal elements in the continuous and discrete cases, by revealing the relation between the principal partition and the canonical partition. We also describe decomposition-type algorithms for the discrete case following the approach of Fujishige and Groenevelt.