论文标题
减少M-Convex集的最小化：算法和应用
Decreasing Minimization on M-convex Sets: Algorithms and Applications
论文作者
论文摘要
本文涉及在M-Convex集中减少最小化的算法和应用，该集合是整体基碱基的整体元素集。基于最近对最小（DEC-MIN）元素的表征，我们开发了一种强烈的多项式算法，用于计算M-Convex集的DEC-MIN元素。 DEC-MIN元素集的矩阵特征也可以计算最低成本DEC-MIN元素。我们的第二个目标是在Matroid和网络优化，资源分配以及（超级）图方向上展示各种应用。我们通过开发图形的DEC分钟内界定方向的结构描述，在很大程度上扩展了半匹配的早期结果。这种表征引起了一种强烈的多项式算法，以找到最小的边缘成本分子方向。
This paper is concerned with algorithms and applications of decreasing minimization on an M-convex set, which is the set of integral elements of an integral base-polyhedron. Based on a recent characterization of decreasingly minimal (dec-min) elements, we develop a strongly polynomial algorithm for computing a dec-min element of an M-convex set. The matroidal feature of the set of dec-min elements makes it possible to compute a minimum cost dec-min element, as well. Our second goal is to exhibit various applications in matroid and network optimization, resource allocation, and (hyper)graph orientation. We extend earlier results on semi-matchings to a large degree by developing a structural description of dec-min in-degree bounded orientations of a graph. This characterization gives rise to a strongly polynomial algorithm for finding a minimum edge-cost dec-min orientation.
