Valuated Matroid Intersection I: Optimality Criteria

DOI10.1137/S0895480195279994MaRDI QIDQ4717566zbMATH 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/S0895480195279994

zbMATH Keywords

bipartite graphindependent assignment problemmatchingweighted 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 II: Algorithms
• Fenchel-type duality for matroid valuations
• Matroid valuation on independent sets

Cited in

(35)

• Fenchel-type duality for matroid valuations
• Discrete convex analysis
• Two-best solutions under distance constraints: The model and exemplary results for matroids
• \(k\)-best solutions under distance constraints in valuated \(\Delta\)-matroids
• Matroid valuation on independent sets
• Note on exchange axioms for valuated matroids and valuated delta-matroids
• A constructive proof for the induction of M-convex functions through networks
• Gross substitutability: an algorithmic survey
• Randomized algorithms for finding the shortest negative cost cycle in networks
• Buyback problem with discrete concave valuation functions
• 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
• 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
• ON THE PIPAGE ROUNDING ALGORITHM FOR SUBMODULAR FUNCTION MAXIMIZATION — A VIEW FROM DISCRETE CONVEX ANALYSIS
• Convexity and Steinitz's exchange property
• Valuated Matroid Intersection II: Algorithms
• 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
• Polynomial-time approximation schemes for maximizing gross substitutes utility under budget constraints
• Optimal matroid bases with intersection constraints: valuated matroids, M-convex functions, and their applications
• On circuit valuation of matroids
• Efficient matching under general constraints
• Efficient and strategy-proof mechanism under general constraints

This page was built for publication: Valuated Matroid Intersection I: Optimality Criteria

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