Simpler exchange axioms for M-concave functions on generalized polymatroids

DOI10.1007/s13160-017-0285-5zbMath1390.90474OpenAlexW2778764888MaRDI QIDQ1742881

Kazuo Murota, Akiyoshi Shioura

Publication date: 12 April 2018

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-017-0285-5

zbMATH Keywords

discrete optimizationpolymatroidexchange propertydiscrete convex analysis

Mathematics Subject Classification ID

Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) (52B40) Combinatorial optimization (90C27)

Related Items

The b‐bibranching problem: TDI system, packing, and discrete convexity, Subdivisions of generalized permutahedra, Equivalence between substitutability and \(\mathrm{M}^\natural\)-concavity for set functions under discrete transfers, Consistency of the doctor-optimal equilibrium price vector in job-matching markets, A survey of fundamental operations on discrete convex functions of various kinds, On basic operations related to network induction of discrete convex functions

Cites Work

• Unnamed Item
• Unnamed Item
• Convexity and Steinitz's exchange property
• Generalized polymatroids and submodular flows
• Fast scaling algorithms for M-convex function minimization with application to the resource allocation problem.
• Gross substitutability: an algorithmic survey
• Time bounds for iterative auctions: a unified approach by discrete convex analysis
• Congestion games viewed from M-convexity
• Verifying gross substitutability.
• Well-layered maps---a class of greedily optimizable set functions
• Submodular functions and optimization.
• M-Convex Function on Generalized Polymatroid
• The Logic of Logistics
• M-Convex Function Minimization by Continuous Relaxation Approach: Proximity Theorem and Algorithm
• Job Matching, Coalition Formation, and Gross Substitutes
• Discrete Convex Analysis
• On Equivalence of M$^\natural$-concavity of a Set Function and Submodularity of Its Conjugate
• A Two-Sided Discrete-Concave Market with Possibly Bounded Side Payments: An Approach by Discrete Convex Analysis
• GROSS SUBSTITUTES CONDITION AND DISCRETE CONCAVITY FOR MULTI-UNIT VALUATIONS: A SURVEY
• A Note on Kelso and Crawford's Gross Substitutes Condition
• Discrete convexity and equilibria in economies with indivisible goods and money