Very sparse integrality-gap conjecture for random hitting set

About 3 years old · traced to

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

val⁡GRval⁡LP→1.\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.

References

Primary source

Gabriel Arpino, Daniil Dmitriev and Nicolo Grometto, “Greedy Heuristics and Linear Relaxations for the Random Hitting Set Problem”, arXiv:2305.05565 (2023).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.