Convexity and Steinitz's exchange property

DOI10.1007/3-540-61310-2_20zbMath1415.90065OpenAlexW2107504654MaRDI QIDQ4645928

Kazuo Murota

Publication date: 11 January 2019

Published in: Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-61310-2_20

zbMATH Keywords

bipartite graphsubmodular functionseparation theoremconcave functionintegral base

Mathematics Subject Classification ID

Integer programming (90C10) Combinatorial optimization (90C27)

Related Items

Algorithmic Aspects of Private Bayesian Persuasion., Discrete convex analysis

Cites Work

• Unnamed Item
• Convexity and Steinitz's exchange property
• Valuated matroids: A new look at the greedy algorithm
• Submodular flow problem with a nonseparable cost function
• Two algorithms for maximizing a separable concave function over a polymatroid feasible region
• Submodular functions and optimization
• Valuated matroids
• Matroid valuation on independent sets
• Well-layered maps and the maximum-degree \(k \times k\)-subdeterminant of a matrix of rational functions
• Finding optimal minors of valuated bimatroids
• Well-layered maps---a class of greedily optimizable set functions
• Theory of submodular programs: A fenchel-type min-max theorem and subgradients of submodular functions
• Lexicographically Optimal Base of a Polymatroid with Respect to a Weight Vector
• A weighted matroid intersection algorithm
• AN ALGORITHM FOR FINDING AN OPTIMAL "INDEPENDENT ASSIGNMENT"
• Valuated Matroid Intersection I: Optimality Criteria
• An Algorithm for Submodular Functions on Graphs
• Convex Analysis