Decreasing minimization on M-convex sets: background and structures

DOI10.1007/s10107-021-01722-2zbMath1504.90120arXiv2007.09616OpenAlexW3208115557MaRDI QIDQ2089794

Kazuo Murota, András Frank

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.09616

zbMATH Keywords

matroidsubmodular optimizationM-convex setbase-polyhedronlexicographic minimization

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27)

Related Items

Strongly Connected Orientation with Minimum Lexicographic Order of Indegrees, Cutoff stability under distributional constraints with an application to summer internship matching, Decreasing minimization on base-polyhedra: relation between discrete and continuous cases

Cites Work

• 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
• On the orientation of graphs
• Two algorithms for maximizing a separable concave function over a polymatroid feasible region
• Discrete convex analysis
• Solving integer programs over monotone inequalities in three variables: A framework for half integrality and good approximations
• Shifted matroid optimization
• A cut-based algorithm for the nonlinear dual of the minimum cost network flow problem
• About strongly polynomial time algorithms for quadratic optimization over submodular constraints
• Decreasing minimization on M-convex sets: algorithms and applications
• Complexity and algorithms for nonlinear optimization problems
• Submodular functions and optimization.
• Maximum semi-matching problem in bipartite graphs
• Theory of Principal Partitions Revisited
• 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
• Optimal flows in networks with multiple sources and sinks
• A good algorithm for lexicographically optimal flows in multi-terminal networks
• Discrete Convex Analysis
• Least Majorized Elements and Generalized Polymatroids
• Density decompositions of networks
• Egalitarian Graph Orientations
• On Convex Minimization over Base Polytopes
• Semi-matchings for bipartite graphs and load balancing
• Inequalities: theory of majorization and its applications