Matroids, briefly
Over the summer, I casually got back into competitive programming. I was really surprised to see that Matroid Intersection is now a topic that shows up in contest problems. In Waterloo, I learned about Matroids in CO450: Combinatorial Optimization, and how problems such as maximum bipartite matching can be modeled with a matroid intersection problem. But, it’s been over 2 years since that course, so I thought I’d review. I will be stating theorems without proof, so it would be nice to look into the references for proofs of the results.
Read more...