Two algorithms for weighted matroid intersection

DOI10.1007/BF02591988zbMath0632.90045OpenAlexW2034977257MaRDI QIDQ3770280

Fred Glover, Carl Brezovec, Cornuéjols, Gérard

Publication date: 1986

Published in: Mathematical Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02591988

zbMATH Keywords

polynomial algorithmscomplexity boundmatroid intersectionsmaximal weight intersection

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10) Combinatorial aspects of matroids and geometric lattices (05B35)

Related Items

A matroid algorithm and its application to the efficient solution of two optimization problems on graphs, A dual approximation approach to weighted matroid intersection, A bound for the symmetric travelling salesman problem through matroid formulation, Multi-objective matroid optimization with ordinal weights, The \(b\)-branching problem in digraphs, Matroid Intersection under Restricted Oracles, Unnamed Item, The minimum spanning tree problem with conflict constraints and its variations, Color constrained combinatorial optimization problems, On the generality of the greedy algorithm for solving matroid base problems, On finding optimal polytrees, Crashing a maximum-weight complementary basis, Paroids: A canonical format for combinatorial optimization, How to allocate review tasks for robust ranking, Paroid search: Generic local combinatorial optimization, Exact and approximation algorithms for weighted matroid intersection

Cites Work

• Unnamed Item
• Unnamed Item
• A matroid algorithm and its application to the efficient solution of two optimization problems on graphs
• Solving the linear matroid parity problem as a sequence of matroid intersection problems
• Matroid Intersection
• A weighted matroid intersection algorithm
• AN ALGORITHM FOR FINDING AN OPTIMAL "INDEPENDENT ASSIGNMENT"
• A PRIMAL APPROACH TO THE INDEPENDENT ASSIGNMENT PROBLEM