On contention resolution for the hypergraph matching, knapsack, and $k$-column sparse packing problems
Fuente:
arXiv
Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866913292178423808 |
|---|---|
| author | Sergeev, Ivan |
| author_facet | Sergeev, Ivan |
| contents | 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 $\frac{1-e^{-k}}{k}$ and provide a monotone $\left(b,\frac{1-e^{-bk}}{bk}\right)$-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 $\frac{1-e^{-2}}{2}$ and provide several monotone contention resolution schemes: a $\frac{1-e^{-2}}{2}$-balanced scheme for instances where all item sizes are strictly bigger than $\frac{1}{2}$, a $\frac{4}{9}$-balanced scheme for instances where all item sizes are at most $\frac{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 $\left(2k+o\left(k\right)\right)$-approximation algorithm for $k$-CS-PIP based on the strengthened LP relaxation presented in Brubach et al. (2019) to obtain a $\frac{1}{4k+o\left(k\right)}$-balanced contention resolution scheme and hence a $\left(4k+o\left(k\right)\right)$-approximation algorithm for $k$-CS-PIP based on the natural LP relaxation. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_00041 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On contention resolution for the hypergraph matching, knapsack, and $k$-column sparse packing problems Sergeev, Ivan Data Structures and Algorithms Optimization and Control 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 $\frac{1-e^{-k}}{k}$ and provide a monotone $\left(b,\frac{1-e^{-bk}}{bk}\right)$-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 $\frac{1-e^{-2}}{2}$ and provide several monotone contention resolution schemes: a $\frac{1-e^{-2}}{2}$-balanced scheme for instances where all item sizes are strictly bigger than $\frac{1}{2}$, a $\frac{4}{9}$-balanced scheme for instances where all item sizes are at most $\frac{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 $\left(2k+o\left(k\right)\right)$-approximation algorithm for $k$-CS-PIP based on the strengthened LP relaxation presented in Brubach et al. (2019) to obtain a $\frac{1}{4k+o\left(k\right)}$-balanced contention resolution scheme and hence a $\left(4k+o\left(k\right)\right)$-approximation algorithm for $k$-CS-PIP based on the natural LP relaxation. |
| title | On contention resolution for the hypergraph matching, knapsack, and $k$-column sparse packing problems |
| topic | Data Structures and Algorithms Optimization and Control |
| url | https://arxiv.org/abs/2404.00041 |