Efficiently Coloring the Intersection of a General Matroid and Combinatorial Matroids

Abstract

This paper shows a polynomial-time algorithm that, given a general matroid $M_1$ and $k-1$ partition matroids $M_2,\dots ,M_k$, produces a coloring of the intersection $M={\cap }_{i=1}^k{M}_i$ using at most $1+{\sum }_{i=1}^k\left(\ddot{I}‡(M_i)-1\right)$ colors. This is the first polynomial-time $O(k)$-approximation algorithm for matroid intersection coloring where one of the matroids may be a general matroid. Leveraging the fact that most of the standard combinatorial matroids reduce to partition matroids at a loss of a factor of two in the chromatic number, this algorithm also yields a polynomial-time $O(k)$-approximation algorithm for matroid intersection coloring in the case where each of the matroids $M_2,\dots ,M_k$ are one of these standard combinatorial types. Even when $k=2$, the previous best-known approximation ratio was $O(\log n)$ via a reduction to Set Cover.

Topics & keywords