An Optimal Monotone Contention Resolution Scheme for Uniform and Partition Matroids

A common approach to solve a combinatorial optimization problem is to first solve a continous relaxation and then round the fractional solution. For the latter, the framework of contention resolution schemes (or CR schemes) introduced by Chekuri, Vondrak, and Zenklusen, has become a general and successful tool. A CR scheme takes a fractional point $x$ in a relaxation polytope, rounds each coordinate $x_i$ independently to get a possibly non-feasible set, and then drops some elements in order to satisfy the independence constraints. Intuitively, a CR scheme is $c$-balanced if every element $i$ is selected with probability at least $c \cdot x_i$. It is known that general matroids admit a $(1-1/e)$-balanced CR scheme, and that this is (asymptotically) optimal. This is in particular true for the special case of uniform matroids of rank one. In this work, we provide a simple monotone CR scheme with a balancedness factor of $1 - e^{-k}k^k/k!$ for uniform matroids of rank $k$, and show that this is optimal. This result generalizes the $1-1/e$ optimal factor for the rank one (i.e. $k=1$) case, and improves it for any $k>1$. Moreover, this scheme generalizes into an optimal CR scheme for partition matroids.