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 (4)

Strongly Connected Orientation with Minimum Lexicographic Order of Indegrees ⋮ Cutoff stability under distributional constraints with an application to summer internship matching ⋮ A fair and truthful mechanism with limited subsidy ⋮ 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

This page was built for publication: Decreasing minimization on M-convex sets: background and structures