Matroid rank functions and discrete concavity

DOI10.1007/s13160-012-0082-0zbMath1254.90196MaRDI 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 optimization; submodular function; matroid; rank function; discrete concave function

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

90C27: Combinatorial optimization

Related Items

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

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