Decreasing minimization on M-convex sets: algorithms and applications

• 成果类型: Article
• 署名作者: Frank, Andras; Murota, Kazuo
• 署名单位: Eotvos Lorand University; Tokyo Metropolitan University; Research Organization of Information & Systems (ROIS); Institute of Statistical Mathematics (ISM) - Japan
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-021-01711-5
• 发表日期: 2022
• 页码: 1027-1068
• 关键词: submodular functions; graphs; optimization; THEOREM; orientation

摘要

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.