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⁻ᵏk and provide a monotone (b,1-e⁻ᵇᵏbk)-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⁻²2 and provide several monotone contention resolution schemes: a 1-e⁻²2-balanced scheme for instances where all item sizes are strictly bigger than 1/2, a 4/9-balanced scheme for instances where all item sizes are at most 1/2, 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 1/4k+o(k)-balanced contention resolution scheme and hence a (4k+o(k))-approximation algorithm for k-CS-PIP based on the natural LP relaxation.