Extension of M-convexity and L-convexity to polyhedral convex functions

DOI10.1006/aama.2000.0702zbMath1073.90544OpenAlexW2059664817MaRDI QIDQ1841175

Kazuo Murota, Akiyoshi Shioura

Publication date: 2000

Published in: Advances in Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/aama.2000.0702

zbMATH Keywords

combinatorial optimizationmatroidconvex analysisbase polyhedronpolyhedral convex function

Mathematics Subject Classification ID

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

Related Items

Quadratic M-convex and L-convex functions, Unnamed Item, Polyhedra with submodular support functions and their unbalanced simultaneous exchangeability, New characterizations of M-convex functions and their applications to economic equilibrium models with indivisibilities., Recent Developments in Discrete Convex Analysis, Application of M-convex submodular flow problem to mathematical economics, Stability and competitive equilibria in multi-unit trading networks with discrete concave utility functions, Compression of \(\mathrm{M}^\natural\)-convex functions -- flag matroids and valuated permutohedra, Dijkstra's algorithm and L-concave function maximization, A note on \(M\)-convexity in polyhedral split decomposition of distances, Conjugacy relationship between M-convex and L-convex functions in continuous variables, Applications of discrete convex analysis to mathematical economics, Cone superadditivity of discrete convex functions, Directed discrete midpoint convexity, ON THE PIPAGE ROUNDING ALGORITHM FOR SUBMODULAR FUNCTION MAXIMIZATION — A VIEW FROM DISCRETE CONVEX ANALYSIS, Polybasic polyhedra: Structure of polyhedra with edge vectors of support size at most 2, Polynomial-Time Approximation Schemes for Maximizing Gross Substitutes Utility Under Budget Constraints, Substitutes and complements in network flows viewed as discrete convexity, A new way to extend t-norms, t-conorms and negations

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Convexity and Steinitz's exchange property
• A note on Frank's generalized polymatroids
• Valuated matroids: A new look at the greedy algorithm
• Generalized polymatroids and submodular flows
• Submodular flow problem with a nonseparable cost function
• Submodular functions and optimization
• Valuated matroids
• Discrete convex analysis
• Matroid valuation on independent sets
• A capacity scaling algorithm for convex cost submodular flows
• Minimization of an M-convex function
• Notes on L-/M-convex functions and the separation theorems
• Network flow, transportation and scheduling. Theory and algorithms
• Finding optimal minors of valuated bimatroids
• Rings of sets
• M-Convex Function on Generalized Polymatroid
• Submodular systems and related topics
• On the Degree of Mixed Polynomial Matrices
• Valuated Matroid Intersection I: Optimality Criteria
• Valuated Matroid Intersection II: Algorithms
• An Algorithm for Submodular Functions on Graphs
• Delta-Matroids, Jump Systems, and Bisubmodular Polyhedra
• Theory of Matroids
• Matrices and matroids for systems analysis
• Discrete convexity and equilibria in economies with indivisible goods and money
• Relationship of M-/L-convex functions with discrete convex functions by Miller and Favati-Tardella.