Very sparse integrality-gap conjecture for random hitting set

From papers

Let mm be the number of subsets, let pp be the inclusion probability, and let nn be the number of elements. Write valGR\operatorname{val}_{\mathrm{GR}} for the value produced by the greedy algorithm and valLP\operatorname{val}_{\mathrm{LP}} for the linear-programming relaxation. Very sparse conjecture. For mp1mp \ll 1,

valGRvalLP1.\frac{\operatorname{val}_{\mathrm{GR}}}{\operatorname{val}_{\mathrm{LP}}} \to 1.

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

No solutions have been posted yet.