Sparse integrality-gap conjecture for random hitting set
Sparse integrality-gap conjecture for random hitting set
Let be the number of subsets, let be the inclusion probability, and let be the number of elements. Write for the value produced by the greedy algorithm, for the integer-program value, and for the linear-programming relaxation. Let be a constant. Sparse conjecture. For ,
where . This conjecture describes the intermediate-sparsity regime and predicts both asymptotic optimality of the greedy algorithm relative to the integer program and a bounded nontrivial integrality gap. The source formulates it from numerical experiments and gives no resolution.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
Primary source
Gabriel Arpino, Daniil Dmitriev and Nicolo Grometto, “Greedy Heuristics and Linear Relaxations for the Random Hitting Set Problem”, arXiv:2305.05565 (2023).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.