TR-2020-12

Decreasing Minimization on M-convex Sets: Algorithms and Applications

András Frank, Kazuo Murota



Abstract

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 cost dec-min orientation.


Bibtex entry:

@techreport{egres-20-12,
AUTHOR = {Frank, Andr{\'a}s and Murota, Kazuo},
TITLE = {Decreasing Minimization on M-convex Sets: Algorithms and Applications},
NOTE= {{\tt www.cs.elte.hu/egres}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2020},
NUMBER = {TR-2020-12}
}


Last modification: 29.12.2020. Please email your comments to Tamás Király!