On contention resolution for the hypergraph matching, knapsack, and k-column sparse packing problems

The contention resolution framework is a versatile rounding technique used as a part of the relaxation and rounding approach for solving constrained submodular function maximization problems. We apply this framework to the hypergraph matching, knapsack, and k-column sparse packing problems. In the hypergraph matching setting, we adapt the technique of Guruganesh, Lee (2018) to non-constructively prove that the correlation gap is at least 1-e^-kk and provide a monotone (b, 1-e^-bkbk) -balanced contention resolution scheme, generalizing the results of Bruggmann, Zenklusen (2019). For the knapsack problem, we prove that the correlation gap of instances where exactly k copies of each item fit into the knapsack is at least 1-e^-22 and provide several monotone contention resolution schemes: a 1-e^-22-balanced scheme for instances where all item sizes are strictly bigger than 12, a 49-balanced scheme for instances where all item sizes are at most 12, and a 0. 279-balanced scheme for instances with arbitrary item sizes. For k-column sparse packing integer programs, we slightly modify the (2k+o (k) ) -approximation algorithm for k-CS-PIP based on the strengthened LP relaxation presented in Brubach et al. (2019) to obtain a 14k+o (k) -balanced contention resolution scheme and hence a (4k+o (k) ) -approximation algorithm for k-CS-PIP based on the natural LP relaxation.