Dense 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 valIP\operatorname{val}_{\mathrm{IP}} for the integer-program value. Let C2C_2 be a constant. Dense conjecture. For mplognmp \gg \log n,

valGRvalIPC2,\frac{\operatorname{val}_{\mathrm{GR}}}{\operatorname{val}_{\mathrm{IP}}} \to C_2,

where 1C2<1.51\leq C_2<1.5. 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

No solutions have been posted yet.