Two algorithms for weighted matroid intersection

DOI10.1007/BF02591988zbMATH Open0632.90045OpenAlexW2034977257MaRDI QIDQ3770280FDOQ3770280

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

Publication date: 1986

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

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

Recommendations

• Efficient theoretic and practical algorithms for linear matroid intersection problems
• scientific article; zbMATH DE number 4068895
• Exact and approximation algorithms for weighted matroid intersection
• A Fast Approximation for Maximum Weight Matroid Intersection
• Exact and approximation algorithms for weighted matroid intersection

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• A weighted matroid intersection algorithm
• Matroid Intersection
• 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
• AN ALGORITHM FOR FINDING AN OPTIMAL "INDEPENDENT ASSIGNMENT"
• A PRIMAL APPROACH TO THE INDEPENDENT ASSIGNMENT PROBLEM

Cited In (32)

• Title not available (Why is that?)
• Crashing a maximum-weight complementary basis
• Title not available (Why is that?)
• How to allocate review tasks for robust ranking
• Multi-objective matroid optimization with ordinal weights
• Matroid Intersection under Restricted Oracles
• The \(b\)-branching problem in digraphs
• Title not available (Why is that?)
• A Fast Approximation for Maximum Weight Matroid Intersection
• A matroid algorithm and its application to the efficient solution of two optimization problems on graphs
• A new algorithm for the intersection of a line with the independent set polytope of a matroid
• An algebraic algorithm for weighted linear matroid intersection
• A dual approximation approach to weighted matroid intersection
• Parallel algorithms for matroid intersection and matroid parity
• The complexity of maximum matroid--greedoid intersection and weighted greedoid maximiza\-tion
• Color constrained combinatorial optimization problems
• On the generality of the greedy algorithm for solving matroid base problems
• Some results on the weights of \(\bigcap\)-structures
• The convex weighting of a graph and an alternative definition of a matroid
• The minimum spanning tree problem with conflict constraints and its variations
• Paroids: A canonical format for combinatorial optimization
• A bound for the symmetric travelling salesman problem through matroid formulation
• On finding optimal polytrees
• Improved Bounds for Matroid Partition and Intersection Algorithms
• Title not available (Why is that?)
• An algorithm for finding a matroid basis which maximizes the product of the weights of the elements
• Exact and approximation algorithms for weighted matroid intersection
• Exact and approximation algorithms for weighted matroid intersection
• Paroid search: Generic local combinatorial optimization
• Title not available (Why is that?)
• A time expanded matroid algorithm for finding optimal dynamic matroid intersections
• Title not available (Why is that?)

This page was built for publication: Two algorithms for weighted matroid intersection

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