Valuated Matroid Intersection II: Algorithms

DOI10.1137/S0895480195280009MaRDI QIDQ4717567zbMATH OpenFDO

Authors Kazuo Murota

Publication date 1 December 1996

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

Full work available at URL https://doi.org/10.1137/S0895480195280009

zbMATH Keywords

bipartite graphprimal-dual-type augmenting algorithmprimal-type cycle-cancelling algorithmvaluated independent assignment problemweighted matroid intersection problem

Mathematics Subject Classification ID

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

Recommendations

• Valuated Matroid Intersection I: Optimality Criteria
• Two algorithms for weighted matroid intersection
• AN EFFICIENT COST SCALING ALGORITHM FOR THE INDEPENDENT ASSIGNMENT PROBLEM
• A weighted independent even factor algorithm
• scientific article; zbMATH DE number 2086910

Cited in

(31)

• Fenchel-type duality for matroid valuations
• Discrete convex analysis
• Two-best solutions under distance constraints: The model and exemplary results for matroids
• Gross substitutability: an algorithmic survey
• Randomized algorithms for finding the shortest negative cost cycle in networks
• Applications of discrete convex analysis to mathematical economics
• A capacity scaling algorithm for M-convex submodular flow
• Extension of M-convexity and L-convexity to polyhedral convex functions
• Two algorithms for valuated \(\Delta\)-matroids
• Shortest bibranchings and valuated matroid intersection
• Computing the maximum degree of minors in mixed polynomial matrices via combinatorial relaxation
• Relationship of two formulations for shortest bibranchings
• Matroid bases with cardinality constraints on the intersection
• Computing Walrasian equilibria: fast algorithms and structural properties
• A weighted independent even factor algorithm
• Combinatorial auctions with decreasing marginal utilities
• Recent developments in discrete convex analysis
• Computing the maximum degree of minors in mixed polynomial matrices via combinatorial relaxation
• Beyond JWP: a tractable class of binary VCSPs via M-convex intersection
• scientific article; zbMATH DE number 4068895 (Why is no real title available?)
• Valuated Matroid Intersection I: Optimality Criteria
• Valuated matroid-based algorithm for submodular welfare problem
• A framework of discrete DC programming by discrete convex analysis
• A tractable class of binary VCSPs via M-convex intersection
• When are welfare guarantees robust?
• Matroidal choice functions
• Optimal matroid bases with intersection constraints: valuated matroids, M-convex functions, and their applications
• On circuit valuation of matroids
• An efficient algorithm for minimizing M-convex functions under a color-induced budget constraint
• Characterization and algorithm for bivariate multi-unit assignment valuations
• Efficient matching under general constraints

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4717567)