2024/03/24 by Ivan Sergeev, Sergeev, Ivan
Engineering · #Optimization and Packing Problems #RFID technology advancements #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2404.00041
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 \frac1-e-kk and provide a monotone (b,\frac1-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 \frac1-e-22 and provide several monotone contention resolution schemes: a \frac1-e-22-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.