Decreasing minimization on M-convex sets: algorithms and applications
From MaRDI portal
Publication:2089795
DOI10.1007/S10107-021-01711-5zbMATH Open1504.90121arXiv2007.09618OpenAlexW3207212991MaRDI QIDQ2089795FDOQ2089795
Authors: András Frank, Kazuo Murota 
Publication date: 24 October 2022
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
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 edge-cost dec-min orientation.
Full work available at URL: https://arxiv.org/abs/2007.09618
Recommendations
- Decreasing minimization on M-convex sets: background and structures
- Fair integral submodular flows
- Fast scaling algorithms for M-convex function minimization with application to the resource allocation problem.
- Decreasing minimization on base-polyhedra: relation between discrete and continuous cases
- Minimization of an M-convex function
network flowsresource allocationgraph orientationpolynomial algorithmM-convex setdecreasing minimization
Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27)
Cites Work
- Title not available (Why is that?)
- Discrete Convex Analysis
- Title not available (Why is that?)
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- On the degrees of the vertices of a directed graph
- Submodular functions and optimization.
- Connections in combinatorial optimization
- On Orientations, Connectivity and Odd-Vertex-Pairings in Finite Graphs
- Minconvex Factors of Prescribed Size in Graphs
- Minimizing a Submodular Function on a Lattice
- Title not available (Why is that?)
- A faster strongly polynomial time algorithm for submodular function minimization
- A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
- Title not available (Why is that?)
- A strongly polynomial minimum cost circulation algorithm
- Generalized polymatroids and submodular flows
- Augmenting Graphs to Meet Edge-Connectivity Requirements
- About strongly polynomial time algorithms for quadratic optimization over submodular constraints
- Matroid Intersection
- Robbins's Theorem for Mixed Multigraphs
- A generalization of Hungarian method and Hall's theorem with applications in wireless sensor networks
- Semi-matchings for bipartite graphs and load balancing
- On the orientation of graphs
- On the orientation of graphs and hypergraphs
- Minimal edge-coverings of pairs of sets
- A Survey on Covering Supermodular Functions
- The Greedy Procedure for Resource Allocation Problems: Necessary and Sufficient Conditions for Optimality
- Discrete convex analysis
- Approximate min-max theorems for Steiner rooted-orientations of graphs and hypergraphs
- Title not available (Why is that?)
- Complexity and algorithms for nonlinear optimization problems
- Optimal flows in networks with multiple sources and sinks
- A good algorithm for lexicographically optimal flows in multi-terminal networks
- Lexicographically Optimal Base of a Polymatroid with Respect to a Weight Vector
- Structures of polyhedra determined by submodular functions on crossing families
- Egalitarian graph orientations
- Density decompositions of networks
- Recent results on well-balanced orientations
- M-convex function minimization by continuous relaxation approach: proximity theorem and algorithm
- Shifted matroid optimization
- Maximum semi-matching problem in bipartite graphs
- Discrete Newton's algorithm for parametric submodular function minimization
- Supermodularity in unweighted graph optimization. I: Branchings and matchings
Cited In (4)
This page was built for publication: Decreasing minimization on M-convex sets: algorithms and applications
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2089795)
