论文标题
减小M-Convex集的最小化：背景和结构
Decreasing Minimization on M-convex Sets: Background and Structures
论文作者
论文摘要
目前的工作是一对论文的第一个成员，该论文涉及一组积分向量的减少最小的（DEC-MIN）元素，如果其最大的成分尽可能小，则载体是Dec-Min的，下一个最大的组件是尽可能小的。这个离散的概念及其分数对应物在文献中以各种名称出现。 我们认为的域是一个M-Convex集，即积分基层的积分元素集。分数和离散案例之间的一个基本差异是，基层始终具有独特的DEC-MIN元素，而M-Convex集合的一组DEC-MIN元素则可以在此处借助“典型链”来描述。结果，我们证明了这一集合是通过将其碱基的特征向量与积分向量转换来引起的。 通过依靠这些特征，我们证明元素是Dec-Min的，并且仅当其组件的正方形和最小值时，属性会导致新型的Min-Max定理。如伴侣论文所示，这些特征还引起了强烈多项式算法，以及在资源分配，网络流，矩阵和图形方向问题的几个应用中，实际上为本研究提供了主要动机。特别是，我们证明了图形方向的猜想。
The present work is the first member of a pair of papers concerning decreasingly-minimal (dec-min) elements of a set of integral vectors, where a vector is dec-min if its largest component is as small as possible, within this, the next largest component is as small as possible, and so on. This discrete notion, along with its fractional counterpart, showed up earlier in the literature under various names. The domain we consider is an M-convex set, that is, the set of integral elements of an integral base-polyhedron. A fundamental difference between the fractional and the discrete case is that a base-polyhedron has always a unique dec-min element, while the set of dec-min elements of an M-convex set admits a rich structure, described here with the help of a "canonical chain". As a consequence, we prove that this set arises from a matroid by translating the characteristic vectors of its bases with an integral vector. By relying on these characterizations, we prove that an element is dec-min if and only if the square-sum of its components is minimum, a property resulting in a new type of min-max theorems. The characterizations also give rise, as shown in the companion paper, to a strongly polynomial algorithm, and to several applications in the areas of resource allocation, network flow, matroid, and graph orientation problems, which actually provided a major motivation to the present investigations. In particular, we prove a conjecture on graph orientation.
