Valuated Matroid Intersection II: Algorithms
From MaRDI portal
Publication:4717567
DOI10.1137/S0895480195280009zbMath0868.90133MaRDI QIDQ4717567
Publication date: 1 December 1996
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
bipartite graphweighted matroid intersection problemprimal-dual-type augmenting algorithmprimal-type cycle-cancelling algorithmvaluated independent assignment problem
Programming involving graphs or networks (90C35) Combinatorial optimization (90C27) Discrete location and assignment (90B80) Combinatorial aspects of matroids and geometric lattices (05B35)
Related Items
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
