← All problems

Dense integrality-gap conjecture for random hitting set

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

val⁡GRval⁡IP→C2,\frac{\operatorname{val}_{\mathrm{GR}}}{\operatorname{val}_{\mathrm{IP}}} \to C_2,

where 1≤C2<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.

References
  1. 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.