论文标题
减少碱基德拉的最小化：离散和连续病例之间的关系
Decreasing Minimization on Base-Polyhedra: Relation Between Discrete and Continuous Cases
论文作者
论文摘要
本文涉及离散与基本底层降低最小化问题之间的关系。 Fujishige在1980年解决了连续版本（以词汇最佳基础的名称）解决，随后在他的书（1991）中描述了随后的阐述。 DEC-MIN问题的离散对应物（与M-Convex集有关）仅是在最近的作者最近才解决的，具有强烈的多项式算法，不仅要计算单个降低的最小元素，而且还要计算所有降低的最小元素的矩形结构，并降低了最小元素和同意的最小元素和称为规范分区。本文的目的是通过建立新颖的技术结果并整合已知结果，提供有关基本底层连续和离散DEC分子问题之间关系的完整图片。特别是，我们通过揭示主要分区与规范分区之间的关系来得出接近度结果，并断言在连续和离散情况下减少最小元素的几何紧密度。我们还描述了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.
