\(M\)-convex functions and tree metrics

DOI10.1007/BF03167590zbMath1084.90036MaRDI QIDQ1764353

Hiroshi Hirai, Kazuo Murota

Publication date: 24 February 2005

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

zbMATH Keywords

tree metric\(M\)-convex functiondiscrete Hessian matrix

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Related Items

Discrete convexity in joint winner property, Gross substitutability: an algorithmic survey, On the Construction of Substitutes, Unnamed Item, The quadratic M-convexity testing problem, Recent Developments in Discrete Convex Analysis, A framework of discrete DC programming by discrete convex analysis, Optimal Allocation in Combinatorial Auctions with Quadratic Utility Functions, A note on \(M\)-convexity in polyhedral split decomposition of distances, Cone superadditivity of discrete convex functions, Congestion games viewed from M-convexity, A Tractable Class of Binary VCSPs via M-Convex Intersection, A combinatorial formula for principal minors of a matrix with tree-metric exponents and its applications

Cites Work

• Unnamed Item
• Unnamed Item
• Convexity and Steinitz's exchange property
• The tree of life and other affine buildings
• Submodular functions and optimization
• A canonical decomposition theory for metrics on a finite set
• Valuated matroids
• A note on the metric properties of trees
• Quadratic M-convex and L-convex functions
• \(T\)-theory: An overview
• ON DISCRETE HESSIAN MATRIX AND CONVEX EXTENSIBILITY
• Theory of submodular programs: A fenchel-type min-max theorem and subgradients of submodular functions
• A Linear Algebra Proof that the Inverse of a Strictly Ultrametric Matrix is a Strictly Diagonally Dominant Stieltjes Matrix
• Discrete Convex Analysis
• An Algorithm for Submodular Functions on Graphs
• Geometry of cuts and metrics
• Relationship of M-/L-convex functions with discrete convex functions by Miller and Favati-Tardella.