Fenchel-type duality for matroid valuations

DOI10.1007/BF01580075zbMath0920.90124MaRDI QIDQ1290625

Kazuo Murota

Publication date: 15 September 1999

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

zbMATH Keywords

nonlinear integer programmingcombinatorial optimizationdiscrete convex analysisdiscrete separation theoremFenchel-type duality theorysubdifferentials of matroid valuationsvaluated matroid intersection problemweighted matroid intersection problem

Mathematics Subject Classification ID

Integer programming (90C10) Nonlinear programming (90C30) Combinatorial optimization (90C27)

Related Items

Existence of a pure strategy equilibrium in finite symmetric games where payoff functions are integrally concave, Note on exchange axioms for valuated matroids and valuated delta-matroids, Recent Developments in Discrete Convex Analysis, A stronger multiple exchange property for \(\mathrm{M}^{\natural }\)-concave functions, On circuit valuation of matroids, Multiple Exchange Property for M^♮-Concave Functions and Valuated Matroids, Discrete convex analysis

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Convexity and Steinitz's exchange property
• Valuated matroids: A new look at the greedy algorithm
• Submodular functions and optimization
• Valuated matroids
• Faces of dual transportation polyhedra
• The Hirsch Conjecture for Dual Transportation Polyhedra
• Theory of submodular programs: A fenchel-type min-max theorem and subgradients of submodular functions
• On the subdifferential of a submodular function
• A weighted matroid intersection algorithm
• AN ALGORITHM FOR FINDING AN OPTIMAL "INDEPENDENT ASSIGNMENT"
• Valuated Matroid Intersection I: Optimality Criteria
• Valuated Matroid Intersection II: Algorithms
• An Algorithm for Submodular Functions on Graphs
• Convex Analysis