Exact and approximation algorithms for weighted matroid intersection

DOI10.1137/1.9781611974331.CH32MaRDI QIDQ4575609zbMATH OpenOpenAlexFDO

Authors Chien-Chung Huang, Naonori Kakimura, Naoyuki Kamiyama

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://doi.org/10.1137/1.9781611974331.ch32

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
• A Fast Approximation for Maximum Weight Matroid Intersection
• An algebraic algorithm for weighted linear matroid intersection
• Two algorithms for weighted matroid intersection
• Efficient theoretic and practical algorithms for linear matroid intersection problems

Cited in

(23)

• Efficient theoretic and practical algorithms for linear matroid intersection problems
• A dual approximation approach to weighted matroid intersection
• Approximation by lexicographically maximal solutions in matching and matroid intersection problems
• Packing of arborescences with matroid constraints via matroid intersection
• On a weighted linear matroid intersection algorithm by deg-det computation
• Exact and approximation algorithms for weighted matroid intersection
• The complexity of maximum matroid--greedoid intersection and weighted greedoid maximiza\-tion
• The matroid intersection cover problem
• An algebraic algorithm for weighted linear matroid intersection
• Algorithms for the partial inverse matroid problem in which weights can only be increased
• Two algorithms for weighted matroid intersection
• scientific article; zbMATH DE number 4068895 (Why is no real title available?)
• scientific article; zbMATH DE number 26304 (Why is no real title available?)
• Random pseudo-polynomial algorithms for exact matroid problems
• scientific article; zbMATH DE number 1555984 (Why is no real title available?)
• A Fast Approximation for Maximum Weight Matroid Intersection
• Making bipartite graphs DM-irreducible
• Preprocessing under uncertainty: matroid intersection
• An algorithm for weighted fractional matroid matching
• scientific article; zbMATH DE number 7378329 (Why is no real title available?)
• On the Complexity of Recovering Incidence Matrices
• Matroid Intersection under Restricted Oracles
• A weighted-to-unweighted reduction for matroid intersection

This page was built for publication: Exact and approximation algorithms for weighted matroid intersection

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