Very sparse integrality-gap conjecture for random hitting set
Very 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 and for the linear-programming relaxation. Very sparse conjecture. For ,
This conjecture concerns the very sparse regime of the random hitting set problem and predicts that the greedy solution is asymptotically optimal relative to the linear relaxation. The source presents it as a conjecture based on numerical experiments; its resolution is not given.
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.