Graphs and Matroids - Stephen Arndt-Approximation Algorithms for Matroid-Intersection Coloring with Applications to Rota's Basis Conjecture

Abstract:We study algorithmic matroid intersection coloring. We give the first polynomial-time O(1)-approximation algorithm to color O(1) general matroids. Notably, for two general matroids we achieve a 2-approximation. Furthermore, we give a fully polynomial randomized approximation scheme (FPRAS) for coloring the intersection of two matroids when the maximum chromatic number is large. This yields the first polynomial-time algorithm for an asymptotic variant of Rota's Basis Conjecture.