Matroid rank functions and discrete concavity

DOI10.1007/s13160-012-0082-0zbMath1254.90196OpenAlexW2073872397MaRDI QIDQ1926653

Akiyoshi Shioura

Publication date: 28 December 2012

Published in: Japan Journal of Industrial and Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s13160-012-0082-0

zbMATH Keywords

combinatorial optimizationsubmodular functionmatroidrank functiondiscrete concave function

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27)

Related Items

Logarithmic concavity for morphisms of matroids, On the Construction of Substitutes, Lorentzian polynomials, Valuated matroid-based algorithm for submodular welfare problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Generalized polymatroids and submodular flows
• Valuated matroids
• Discrete convex analysis
• Verifying gross substitutability.
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Combinatorial auctions with decreasing marginal utilities
• Submodular functions and optimization.
• M-Convex Function on Generalized Polymatroid
• ON THE PIPAGE ROUNDING ALGORITHM FOR SUBMODULAR FUNCTION MAXIMIZATION — A VIEW FROM DISCRETE CONVEX ANALYSIS
• A Fast Parametric Submodular Intersection Algorithm for Strong Map Sequences
• Discrete Convex Analysis
• From convex optimization to randomized mechanisms
• Maximizing a Submodular Set Function Subject to a Matroid Constraint (Extended Abstract)
• Limitations of Randomized Mechanisms for Combinatorial Auctions
• A Note on Kelso and Crawford's Gross Substitutes Condition