A Fast Approximation for Maximum Weight Matroid Intersection

DOI10.1137/1.9781611974331.CH33MaRDI QIDQ4575610zbMATH OpenOpenAlexFDO

Authors Chandra Chekuri, Kent Quanrud

Publication date 16 July 2018

Published in Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/26c95e7875bfd97f18770d99c8a98b39b22a073d

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25) Combinatorial optimization (90C27)

Recommendations

• Exact and approximation algorithms for weighted matroid intersection
• Exact and approximation algorithms for weighted matroid intersection
• A dual approximation approach to weighted matroid intersection
• scientific article; zbMATH DE number 26304
• Two algorithms for weighted matroid intersection
• An algebraic algorithm for weighted linear matroid intersection
• The complexity of maximum matroid--greedoid intersection and weighted greedoid maximiza\-tion
• scientific article; zbMATH DE number 7768386
• scientific article; zbMATH DE number 1555984
• Efficient algorithms for a family of matroid intersection problems

Cited in

(23)

• A new algorithm for the intersection of a line with the independent set polytope of a matroid
• Fast approximation of matroid packing and covering
• A dual approximation approach to weighted matroid intersection
• Approximation by lexicographically maximal solutions in matching and matroid intersection problems
• Exact and approximation algorithms for weighted matroid intersection
• The complexity of maximum matroid--greedoid intersection and weighted greedoid maximiza\-tion
• Matroidal approximations of independence systems
• Matroid matching: the power of local search
• Improved Bounds for Matroid Partition and Intersection Algorithms
• Two algorithms for weighted matroid intersection
• scientific article; zbMATH DE number 26304 (Why is no real title available?)
• scientific article; zbMATH DE number 1138274 (Why is no real title available?)
• scientific article; zbMATH DE number 1555984 (Why is no real title available?)
• Exact and approximation algorithms for weighted matroid intersection
• Preprocessing under uncertainty: matroid intersection
• Approximate multi-matroid intersection via iterative refinement
• Approximate multi-matroid intersection via iterative refinement
• Matroid Intersection under Restricted Oracles
• Adaptive sparsification for matroid intersection
• Faster matroid partition algorithms
• Breaking O(nr) for matroid intersection
• Deterministic (2/3-)-approximation of matroid intersection using nearly-linear independence-oracle queries
• A weighted-to-unweighted reduction for matroid intersection

This page was built for publication: A Fast Approximation for Maximum Weight Matroid Intersection

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