Valuated Matroid Intersection II: Algorithms

DOI10.1137/S0895480195280009zbMath0868.90133MaRDI QIDQ4717567

Kazuo Murota

Publication date: 1 December 1996

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

zbMATH Keywords

bipartite graphweighted matroid intersection problemprimal-dual-type augmenting algorithmprimal-type cycle-cancelling algorithmvaluated independent 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 (27)

Matroid bases with cardinality constraints on the intersection ⋮ Two algorithms for valuated \(\Delta\)-matroids ⋮ Beyond JWP: A Tractable Class of Binary VCSPs via M-Convex Intersection. ⋮ Shortest bibranchings and valuated matroid intersection ⋮ Gross substitutability: an algorithmic survey ⋮ Randomized algorithms for finding the shortest negative cost cycle in networks ⋮ An efficient algorithm for minimizing M-convex functions under a color-induced budget constraint ⋮ 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 ⋮ On circuit valuation of matroids ⋮ Applications of discrete convex analysis to mathematical economics ⋮ A capacity scaling algorithm for M-convex submodular flow ⋮ Relationship of two formulations for shortest bibranchings ⋮ Combinatorial auctions with decreasing marginal utilities ⋮ 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 ⋮ 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 ⋮ Extension of M-convexity and L-convexity to polyhedral convex functions

This page was built for publication: Valuated Matroid Intersection II: Algorithms