Dense integrality-gap conjecture for random hitting set
Dense 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 and for the integer-program value. Let be a constant. Dense conjecture. For ,
where . This conjecture concerns the dense regime of the random hitting set problem and predicts a constant asymptotic ratio between the greedy and integer-program solutions. It is presented as a numerical conjecture, with no resolution supplied in the source.
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.