Decreasing minimization on M-convex sets: Algorithms and applications
Decreasing minimization on M-convex sets: Algorithms and applications
复制标题
M 凸集的递减最小化：算法和应用
DOI：
10.1007/s10107-021-01711-5
复制
发表时间：
2021
影响因子：
2.7
通讯作者：
K. Murota
中科院分区：
文献类型：
--
作者：
A. Frank;K. Murota
本文研究了M-凸集上的递减极小化算法及其应用。M-凸集是整基多面体的积分元素集。基于最近关于递减极小(DEC-MIN)元的一个刻画，我们提出了一个计算M-凸集的DEC-MIN元的强多项式算法。DEC-MIN元素集合的拟阵特征也使得计算最小代价DEC-MIN元素成为可能。我们的第二个目标是展示在拟阵和网络优化、资源分配和(超)图定向方面的各种应用。我们在很大程度上推广了已有的关于半匹配的结果，给出了图的DEC-MIN度有界方向的结构描述。这一特征给出了一种求最小边代价最小方向的强多项式算法。
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.