Theory Seminar Series: 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.

Bio: Stephen Arndt is a 3rd-year Algorithms, Combinatorics, and Optimization (ACO) PhD Student at Carnegie Mellon University (CMU) in the Operations Research department. Mr. Arndt’s research interests are broadly in approximation algorithms and combinatorial optimization. Mr. Arndt received a B.S. in Computer Science and Mathematics from the University of Pittsburgh, mentored by Kirk Pruhs.