An Optimal Monotone Contention Resolution Scheme for Uniform and Partition Matroids
share
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 · 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^-kk^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.
READ FULL TEXT