Two algorithms for weighted matroid intersection

DOI10.1007/BF02591988MaRDI QIDQ3770280zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

• scientific article; zbMATH DE number 3643026 (Why is no real title available?)
• scientific article; zbMATH DE number 3422402 (Why is no real title available?)
• A PRIMAL APPROACH TO THE INDEPENDENT ASSIGNMENT PROBLEM
• A matroid algorithm and its application to the efficient solution of two optimization problems on graphs
• A weighted matroid intersection algorithm
• AN ALGORITHM FOR FINDING AN OPTIMAL "INDEPENDENT ASSIGNMENT"
• Matroid Intersection
• Solving the linear matroid parity problem as a sequence of matroid intersection problems

Cited in

(32)

• A time expanded matroid algorithm for finding optimal dynamic matroid intersections
• scientific article; zbMATH DE number 1555984 (Why is no real title available?)
• scientific article; zbMATH DE number 1953191 (Why is no real title available?)
• Crashing a maximum-weight complementary basis
• scientific article; zbMATH DE number 1839479 (Why is no real title available?)
• How to allocate review tasks for robust ranking
• Multi-objective matroid optimization with ordinal weights
• The \(b\)-branching problem in digraphs
• Matroid Intersection under Restricted Oracles
• scientific article; zbMATH DE number 123444 (Why is no real title available?)
• 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
• Color constrained combinatorial optimization problems
• On the generality of the greedy algorithm for solving matroid base problems
• The complexity of maximum matroid--greedoid intersection and weighted greedoid maximiza\-tion
• The convex weighting of a graph and an alternative definition of a matroid
• Some results on the weights of \(\bigcap\)-structures
• 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
• An algorithm for finding a matroid basis which maximizes the product of the weights of the elements
• scientific article; zbMATH DE number 7378329 (Why is no real title available?)
• Exact and approximation algorithms for weighted matroid intersection
• Paroid search: Generic local combinatorial optimization
• Exact and approximation algorithms for weighted matroid intersection
• scientific article; zbMATH DE number 3904606 (Why is no real title available?)

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)