Valuated Matroid Intersection I: Optimality Criteria

DOI10.1137/S0895480195279994zbMath0868.90132MaRDI QIDQ4717566

Kazuo Murota

Publication date: 1 December 1996

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

bipartite graphmatchingweighted matroid intersection problemindependent assignment problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27) Discrete location and assignment (90B80) Combinatorial aspects of matroids and geometric lattices (05B35)

Related Items

Convexity and Steinitz's exchange property, Matroid bases with cardinality constraints on the intersection, Note on exchange axioms for valuated matroids and valuated delta-matroids, Two algorithms for valuated \(\Delta\)-matroids, Beyond JWP: A Tractable Class of Binary VCSPs via M-Convex Intersection., A constructive proof for the induction of M-convex functions through networks, Shortest bibranchings and valuated matroid intersection, Gross substitutability: an algorithmic survey, Randomized algorithms for finding the shortest negative cost cycle in networks, A weighted independent even factor algorithm, Computing the maximum degree of minors in mixed polynomial matrices via combinatorial relaxation, Recent Developments in Discrete Convex Analysis, When Are Welfare Guarantees Robust, Valuated matroid-based algorithm for submodular welfare problem, A framework of discrete DC programming by discrete convex analysis, Computing the Maximum Degree of Minors in Mixed Polynomial Matrices via Combinatorial Relaxation, Buyback problem with discrete concave valuation functions, On circuit valuation of matroids, A capacity scaling algorithm for M-convex submodular flow, Relationship of two formulations for shortest bibranchings, Computing Walrasian equilibria: fast algorithms and structural properties, Optimal matroid bases with intersection constraints: valuated matroids, M-convex functions, and their applications, A Tractable Class of Binary VCSPs via M-Convex Intersection, ON THE PIPAGE ROUNDING ALGORITHM FOR SUBMODULAR FUNCTION MAXIMIZATION — A VIEW FROM DISCRETE CONVEX ANALYSIS, Matroidal Choice Functions, Fenchel-type duality for matroid valuations, Discrete convex analysis, Two-best solutions under distance constraints: The model and exemplary results for matroids, Polynomial-Time Approximation Schemes for Maximizing Gross Substitutes Utility Under Budget Constraints, Extension of M-convexity and L-convexity to polyhedral convex functions