A stronger multiple exchange property for M^ -concave functions

DOI10.1007/S13160-017-0278-4zbMATH Open1397.90333arXiv1706.09222OpenAlexW2963464777MaRDI QIDQ1742897FDOQ1742897

Authors: Kazuo Murota 

Publication date: 12 April 2018

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

Abstract: The multiple exchange property for matroid bases has recently been generalized for valuated matroids and M${}^{atural}$-concave set functions. This paper establishes a stronger form of this multiple exchange property that imposes a cardinality condition on the exchangeable subset. The stronger form immediately implies the defining exchange property of M${}^{atural}$-concave set functions, which was not the case with the recently established multiple exchange property without the cardinality condition.

Full work available at URL: https://arxiv.org/abs/1706.09222

Recommendations

• Multiple Exchange Property for M^♮-Concave Functions and Valuated Matroids
• On convex and *-concave multifunctions
• Simpler exchange axioms for M-concave functions on generalized polymatroids
• Properties of exponentially \(m\)-convex functions
• Strongly exponentially convex functions and their properties
• Strong \(m\)-convexity of set-valued functions
• Higher order strongly \(m\)-convex functions
• Strongly reciprocally \(p\)-convex functions and some inequalities
• On \(\mathscr{M}\)-convex functions
• The \(n\)-exponential convexity for majorization inequality for functions of two variables and related results

zbMATH Keywords

combinatorial optimizationmatroidexchange propertydiscrete convex analysis

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Cites Work

• Discrete Convex Analysis
• Walrasian equilibrium with gross substitutes
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Submodular functions and optimization.
• Job Matching, Coalition Formation, and Gross Substitutes
• Recent developments in discrete convex analysis
• Valuated matroids
• \(M\)-convex function on generalized polymatroid
• Valuated matroids: A new look at the greedy algorithm
• Applications of discrete convex analysis to mathematical economics
• GROSS SUBSTITUTES CONDITION AND DISCRETE CONCAVITY FOR MULTI-UNIT VALUATIONS: A SURVEY
• Title not available (Why is that?)
• Fenchel-type duality for matroid valuations
• A stronger multiple exchange property for \(\mathrm{M}^{\natural }\)-concave functions

Cited In (3)

• A stronger multiple exchange property for \(\mathrm{M}^{\natural }\)-concave functions
• Title not available (Why is that?)
• Multiple Exchange Property for M^♮-Concave Functions and Valuated Matroids

This page was built for publication: A stronger multiple exchange property for \(\mathrm{M}^{\natural }\)-concave functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1742897)