Decreasing minimization on M-convex sets: algorithms and applications
From MaRDI portal
Publication:2089795
DOI10.1007/s10107-021-01711-5zbMath1504.90121arXiv2007.09618OpenAlexW3207212991MaRDI QIDQ2089795
Publication date: 24 October 2022
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2007.09618
resource allocationpolynomial algorithmnetwork flowsgraph orientationM-convex setdecreasing minimization
Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27)
Related Items
Strongly Connected Orientation with Minimum Lexicographic Order of Indegrees, Decreasing minimization on M-convex sets: background and structures, Decreasing minimization on base-polyhedra: relation between discrete and continuous cases
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A generalization of Hungarian method and Hall's theorem with applications in wireless sensor networks
- Recent results on well-balanced orientations
- Approximate min-max theorems for Steiner rooted-orientations of graphs and hypergraphs
- A faster strongly polynomial time algorithm for submodular function minimization
- A strongly polynomial minimum cost circulation algorithm
- Generalized polymatroids and submodular flows
- On the orientation of graphs
- Discrete convex analysis
- On the orientation of graphs and hypergraphs
- Shifted matroid optimization
- A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Minimal edge-coverings of pairs of sets
- About strongly polynomial time algorithms for quadratic optimization over submodular constraints
- Discrete Newton's algorithm for parametric submodular function minimization
- Complexity and algorithms for nonlinear optimization problems
- On the degrees of the vertices of a directed graph
- Submodular functions and optimization.
- Maximum semi-matching problem in bipartite graphs
- A Survey on Covering Supermodular Functions
- M-Convex Function Minimization by Continuous Relaxation Approach: Proximity Theorem and Algorithm
- A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions
- Matroid Intersection
- On Orientations, Connectivity and Odd-Vertex-Pairings in Finite Graphs
- Structures of polyhedra determined by submodular functions on crossing families
- Minconvex Factors of Prescribed Size in Graphs
- The Greedy Procedure for Resource Allocation Problems: Necessary and Sufficient Conditions for Optimality
- Lexicographically Optimal Base of a Polymatroid with Respect to a Weight Vector
- Robbins's Theorem for Mixed Multigraphs
- Augmenting Graphs to Meet Edge-Connectivity Requirements
- Optimal flows in networks with multiple sources and sinks
- A good algorithm for lexicographically optimal flows in multi-terminal networks
- Minimizing a Submodular Function on a Lattice
- Discrete Convex Analysis
- Supermodularity in Unweighted Graph Optimization I: Branchings and Matchings
- Density decompositions of networks
- Egalitarian Graph Orientations
- Semi-matchings for bipartite graphs and load balancing
